Лучший способ найти в массиве, если есть X + Y = S

Question

Как лучше всего проверить в массиве, если в массиве с именем A есть 2 числа X, Y, где X + Y = S. S может быть любым числом (необязательно существует в A).

Я сказал, давайте отсортируем массив, который стоит O (nlogn) для худшего случая , тогда давайте возьмем 2 указателя для первого элемента и еще один указатель на последний элемент.

Начало сравнение если указатель 1 + указатель 2. если результат больше, чем уменьшить указатель 2 на 1. если результат меньше, чем увеличить указатель 1 на 1 ... пока мы не переместимся на все элементы в A.

Сложность по времени: nlogn + n (Худший случай для перемещения в 2 указателя) = nlogn.

есть ли лучшее решение?

Answer 1

Вы можете создать набор на основе ха sh и добавить в него все элементы из А. Затем вы можете перебрать элементы A и проверить, существует ли S - A_i в этом наборе. Предполагая, что в O (1) содержатся и помещены операции над множествами, основанными на ha sh, вы решите свою проблему в O (n).