Найдите пары чисел чисел в массиве со всеми парами, дающими ту же сумму

Question

Предположим, что существует массив размером N (N всегда четный). Учитывая, что все элементы массива образуют пару, которая дает такую ​​же сумму при добавлении. Найдите сумму. Это определенно не домашнее задание. Например:

A = {1,4,3,2,5,6,8,7}. ans = 9, потому что {(1,8), (2,7), (3,6), (4,5)} образуют пары сумм 9.

Также могут быть дубликаты. B = {3,4,5,3,4,5}. ANS = 8

То, что я пытался это

1) Сортировка массива = O (NlogN).

2) найдите сумму min и max отсортированного массива. Это сумма, требуемая, потому что, если это что-то другое, кроме этих 2, будет по крайней мере одна пара, которая не может быть сформирована с одинаковой суммой. Надеюсь, я поняла.

Теперь мой вопрос, может ли это быть сделано в линейном времени как-то? Хеширование номеров напрямую не было бы достаточно, потому что «Сумма» не известна заранее.

Answer 1

Сделайте O (n) -проход через набор чисел, чтобы найти min и max и поместить все числа в хэш-таблицу. Вычислить целевую сумму t = max + min. Затем сделайте второй O (n) -проход через набор чисел; для номера x, вычислите y = t-x, ищите y в хеш-таблице, и если он найден, сообщите об этой паре. Что касается дублирования, вы также можете сохранить количество чисел в хеш-таблице.

Answer 2

Найдите сумму массива, удвойте ее и разделите на N.