Дан массив S из n действительных чисел, а также число x. Как за время O(nlogn) определить, можно ли представить х в виде суммы двух элементов из S?

Question

[Victor]

Можно ли придумать алгоритм за время О(nlogn), я смог придумать только перебор сумм по два элемента.

Answer 1

[Mrrl]

1) сортируете массив
2) пускаете два указателя - один с начала, другой с конца. Если сумма элементов под ними меньше X - увеличиваете первый, если больше - уменьшаете второй. Если равна - вы победили, возьмите приз с полки.
3) если указатели встретились, а сумма так ни разу и не равнялась X - то проиграли, можно стреляться.

Comments

[LittleFatNinja]

пффф сложность вашего алгоритма где то O(NlogN + N)

[Mrrl]

LittleFatNinja: Меньшее слагаемое в асимптотике поглощается бОльшим. Так что O(NlogN + N)=O(NlogN).

Answer 2

[Виталий Витренко]

Сортируем массив и потом от i = 0 до N ищем в массиве с помощью бинарного поиска число x-S[i]. Если нашли, выходим из цикла и сообщаем о положительном результате.