Сходимся с двух концов

Проверить каждую пару элементов стоит O(n²), и урок про Big-O показал, как быстро это растёт. Когда данные отсортированы или тебе важны только соседние элементы, два подвижных маркера за один проход делают то, на что вложенным циклам нужно n² шагов.

У тебя есть прайс-лист, уже отсортированный от дешёвого к дорогому, и подарочная карта на точную сумму. Нужно найти два товара, цены которых в сумме дают ровно эту сумму, чтобы потратить карту до копейки.

Первое, что приходит в голову: перебрать все пары. Товар 1 с товаром 2, товар 1 с товаром 3 и так далее. Для короткого списка это нормально. Для списка из миллиона цен это миллион на миллион пар, та самая ловушка O(n²) из урока 09.

Но список отсортирован, и это всё меняет. Благодаря порядку можно отбрасывать целые части списка, не проверяя их, и найти ответ за один проход.

Возьми первый тест: цены [1, 3, 4, 6, 8] и нужная сумма 10. Поставь одну метку на самую дешёвую цену, 1, а другую на самую дорогую, 8. Вместе они дают 9, это мало.

1 не дотягивает до 10 даже вместе с 8, самой большой ценой. С любой ценой поменьше ей не хватит ещё больше. Значит, 1 не входит ни в один ответ, и её можно отбросить: левая метка переходит на 3. Теперь 3 + 8 = 11, это много. То же рассуждение с другой стороны: 8 слишком велика даже с самой маленькой из оставшихся цен, отбрасываем её, и правая метка переходит на 6. Дальше 3 + 6 = 9, снова мало, и левая метка переходит на 4. Наконец 4 + 6 = 10. Пара найдена.

Каждый сдвиг отбрасывал одну цену вместе со всеми парами, которые она могла составить, и ничего не проверялось дважды. Хватило четырёх сумм вместо всех десяти пар.

Поставь маркер lo на самый дешёвый товар, а маркер hi на самый дорогой. Сложи две цены, на которые они указывают.

• Сумма равна цели: пара найдена, готово.
• Сумма слишком мала: увеличить её можно, только взяв товар подороже вместо дешёвого. Сдвинь lo на одну позицию вправо.
• Сумма слишком велика: сдвинь hi на одну позицию влево, чтобы сумма уменьшилась.

Каждый шаг безопасен, потому что список отсортирован. Пусть сумма мала. Тогда nums[lo] не дотягивает до цели даже вместе с самой дорогой из оставшихся цен, nums[hi]. С остальными, более дешёвыми, он не дотянет тем более. Значит, nums[lo] не входит ни в одну подходящую пару, и его можно отбросить. Останавливайся, когда маркеры встретятся.

Проследим на [1, 3, 4, 6, 8] с целью 10. lo указывает на 1, hi на 8: сумма 9, мало, двигаем lo. lo на 3, hi на 8: сумма 11, много, двигаем hi. lo на 3, hi на 6: сумма 9, мало, двигаем lo. lo на 4, hi на 6: сумма 10, нашли. Ответ: позиции 2 и 3.

Время O(n): каждый маркер движется только внутрь, поэтому вместе они делают не больше n шагов. Память O(1): две переменные с индексами, и ничего не растёт вместе со входом. Если список сначала нужно отсортировать, добавь O(n log n) на сортировку.

Сравни с подходом на хеше из урока 18. Он тоже находит пару за O(n) по времени, но тратит O(n) памяти на множество. На уже отсортированных данных два указателя дают ту же скорость и не требуют лишней памяти.

Сверка платежей: в журнале операций, отсортированном по сумме, ищут два исходных списания, которые вместе дают сумму возврата. Биржевой стакан (список заявок, упорядоченный по цене) сводит заявку на покупку с заявкой на продажу. Системы антифрода (поиска мошенничества) и удаления дубликатов ищут в отсортированных записях пару, которая отличается не больше чем на допустимую величину. Везде, где сопоставляют деньги или упорядоченные записи, задача выглядит одинаково: отсортированный вход и поиск пары. Решают её двумя указателями.