Как разработать алгоритм для нахождения двух элементов, сумма которых дает x?

Question

[Relocatik]

Помогите решить данную задачу, ничего не приходит в голову

Comments

[jcmvbkbc]

ничего не приходит в голову

Что, даже тупое решение, не укладывающееся в O(n lg n) -- попробовать все возможные пары чисел из S?

Answer 1

[Karpion]

Сначала упорядочим множество (массив) S по возрастанию.
Затем берём два крайних элемента, считаем их сумму. Допустим, сумма больше, чем нужно - тогда отбрасываем правый (самый большой) элемент; а если меньше - то самый левый (ну, не отбрасываем - а сдвигаем указатель к центру массива). И повторяем - пока не получится нужная сумма или пока элементы не закончатся.

Answer 2

[Рональд Макдональд]

На фриланс, там "помогут".

Answer 3

[Rsa97]

Фантастический способ:
Изучить O-нотацию.
Изучить различные алгоритмы с их оценкой сложности в O-нотации.
Подобрать необходимые алгоритмы и провести их композицию в свой алгоритм, решающий задачу.

Реальный способ:
Бегать по всем форумам с просьбой помочь, авось кто и откликнется.

P.S. Задача, кстати, примитивная, в два действия, первое O(n log n), второе O(n).

Comments

[jcmvbkbc]

При желании можно даже уложиться в O(n)

[Lynn «Кофеман»]

jcmvbkbc, вот тут мне стало любопытно.
С дополнительной памятью под хэш?

[jcmvbkbc]

Алексей Тен, ага. В задании только ограничение на время.

Answer 4

[pulk]

В условии ничего не сказано про использование дополнительной памяти, поэтому можно ее решить за O(N).
hashtable = {}
for x in X:
y = S - x
if y in hashtable:
return x, y
hashtable[x] = 0