Sorted Two Sum — это небольшой вариант базовой задачи Two Sum. После FizzBuzz оригинальная Two Sum — типичная задача для новичков.
Две суммы выглядят следующим образом:
Дав массив целых чисел, найдите два числа, которые в сумме составляют целевое число.
Two Sum, вероятно, является тем местом, где большинство программистов впервые видят, как можно оптимизировать решения. Большинство новичков начинают с грубой силы, находя все возможные комбинации и проверяя, соответствует ли она цели.
Новички быстро поймут, что брутфорс работает... но не проходит все тесты на Leetcode. Это недостаточно быстро, если длина массива исчисляется сотнями или даже тысячами.
Самое быстрое решение - создать хеш-таблицу (объект в javascript).
Сумма двух отсортированных
К предварительно отсортированной задаче о двух суммах подходят совсем по-другому. Хотя вы все еще можете использовать хэш-таблицу, это уже не самое быстрое решение. Слово SORTED, вероятно, является одним из самых важных ключевых слов в алгоритмах. Это полностью меняет то, как вам нужно думать о проблеме. Каждый раз, когда вы видите SORTED, вы должны думать о бинарном поиске или указателях (по крайней мере, при работе с массивами).
Вот как работают указатели:
Вы создаете «указатель» в начале и конце массива, которые по сути являются опорными точками. Я называю их левыми и правыми.
Они продолжают двигаться к середине, пока не пересекутся. Логика такова, что могут произойти три вещи.
Значение левого указателя + значение правого указателя может быть:
- Равно цели (отлично! мы закончили)
- Меньше, чем цель
- Больше, чем цель
Если объединенные значения меньше целевого, нам нужно переместить указатель к центру (левый указатель вправо). Это потому, что мы точно знаем, что следующее число больше или равно текущему левому указателю.
Мы можем сделать то же самое, если комбинированное значение больше целевого. Мы просто перемещаем правый указатель к середине. В приведенном выше примере цель равна 9. Наше текущее комбинированное значение равно 2 + 15, что равно 17. Следовательно, мы перемещаем правый указатель к середине.
Теперь у нас меньшее значение! Мы продолжаем перемещать указатели влево или вправо, пока не найдем значение или не выйдем из цикла.
2+7 соответствует нашей цели!
