Два указателя
Два указателя идут навстречу из концов отсортированного массива — пара с нужной суммой находится за один проход.
1function findPairWithSum(arr: number[], target: number): [number, number] | null {2 let left = 03 let right = arr.length - 14 5 while (left < right) {6 const sum = arr[left] + arr[right]7 if (sum === target) return [left, right]8 if (sum < target) left++9 else right--10 }11 12 return null13}Проблема
Найти пару чисел с заданной суммой в отсортированном массиве. Вложенный перебор — O(n²); хеш-таблица — O(n) с лишней памятью. Сортировка даёт третий путь: два указателя без дополнительной памяти.
Что вы видите
Указатели L и R начинают с краёв. Сумма меньше цели — левое число безнадёжно мало (даже с максимумом справа), двигаем L. Больше — правое безнадёжно велико, двигаем R. Каждый шаг исключает ровно один элемент.
Как это работает
Инвариант: ответ, если он есть, всегда между L и R. Отсортированность гарантирует, что вычеркнутый элемент не может входить ни в одну подходящую пару. Поэтому n−1 сравнений хватает.
Пошаговый разбор
- 01
Старт
L = 0, R = n−1 — вся массив.
- 02
Сравнение
arr[L] + arr[R] против цели.
- 03
Меньше
Цель слишком велика для arr[L] — L++.
- 04
Больше
Цель слишком мала для arr[R] — R−-.
- 05
Встреча
L ≥ R — пары нет.
Complexity и ограничения
Массив должен быть отсортирован. O(n) времени, O(1) памяти.
Edge cases
- Пара — первые элементы
Одно сравнение, O(1).
- Пары нет
Указатели встретятся за n−1 шаг.
- Дубликаты
Вернётся первая встреченная пара.
Где встречается в реальности
Сумма двух чисел
Классика собеседований: отсортированный вход решается без хеш-таблицы.
Корреляция выборок
Слияние/пересечение отсортированных последовательностей — та же схема.
Контейнеры с водой
Задача про максимум воды между стенками — два указателя с другим правилом движения.
Связанные алгоритмы
«Пара с суммой за один проход — как?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.