Opposite-Direction Pointers

Задача «найти в массиве пару с суммой X» решается в лоб двумя вложенными циклами: $O(n^2)$ пар. На тысяче элементов это миллион операций и доли секунды, на миллионе — $10^{12}$ операций и часы. При этом если массив отсортирован, перебор ведёт себя так, будто порядка нет: он проверяет пары, про которые заранее известно, что они не подходят.

То же самое в задачах «наибольшая площадь между стенками», «сколько воды соберётся», «палиндром ли строка»: наивное решение сравнивает всё со всем, хотя структура входа позволяет за один шаг отбрасывать сразу целые группы вариантов.

Отсюда весь алгоритм: ставим указатели на концы и на каждом шаге решаем, какой конец «безнадёжен». Сдвиг одного указателя убирает из рассмотрения не один вариант, а целую полосу — поэтому шагов оказывается $n$, а не $n^2$.

индекс   0   1   2   3
высота   2   8   5   7

             #
             #       #
             #   #   #
         #   #   #   #
        ---------------
         L           R

площадь = min(2, 7) * (3 - 0) = 6

Максимум найден на втором шаге и равен 14. Проверено при этом четыре пары из шести — и чем длиннее массив, тем сильнее экономия: проверяется $n$ пар вместо $n(n-1)/2$.

left, right = 0, len(a) - 1
best = 0

while left < right:
    best = max(best, value(a, left, right))

    if a[left] < a[right]:      # левый конец ограничивает ответ
        left += 1
    else:
        right -= 1

return best

• Инвариант: лучший ответ лежит среди пар с обоими концами внутри отрезка [left, right].
• Время — $O(n)$: каждый шаг сдвигает один из указателей, а сдвигов не больше $n$.
• Память — $O(1)$: хранятся два индекса и текущий лучший ответ.
• Предусловие — массив отсортирован либо величина, по которой принимается решение, монотонна по границе.

Докажем шаг для задачи о воде. Пусть $h[L]<h[R]$ и мы сдвигаем $L$. Отбрасываются все пары вида $(L,k)$ при $k<R$. Для любой такой пары высота не больше $h[L]$, а ширина строго меньше $R-L$, значит её площадь строго меньше уже посчитанной $\min (h[L],h[R])\cdot (R-L)$. Ни один отброшенный вариант не был лучше текущего — сдвиг безопасен.

То же рассуждение для пары с суммой в отсортированном массиве: если $a[L]+a[R]<X$, то и для всех $k<R$ сумма $a[L]+a[k]$ меньше $X$, потому что массив упорядочен. Левый элемент не образует нужной пары ни с кем из оставшихся, и сдвигать его безопасно.

Отдельный параметр — что делать при равенстве. В задаче о паре равенство означает найденный ответ; в задаче о воде при равных стенках можно двигать любую, и корректность не страдает; в задаче о тройке равенство требует ещё и пропуска дубликатов, иначе ответ повторится.

• Массив не отсортирован. Приём молча выдаёт неверный ответ, а не падает — на случайных тестах это не всегда видно.
• Условие цикла. while left < right — пара из элемента с самим собой обычно запрещена; left <= right нужно только там, где одиночный элемент допустим.
• Дубликаты в тройках. Без явного пропуска повторов одна и та же тройка попадает в ответ несколько раз.
• Сортировка ломает индексы. Если в ответе нужны позиции из исходного массива, сортировать приходится пары «значение, индекс».
• Переполнение при сумме. В языках с ограниченным целым типом сумма двух больших элементов переполняется раньше, чем сравнивается с целью.

1. Почему в задаче о воде нужно двигать меньшую стенку, а не большую?
2. Пара с суммой X в отсортированном массиве — напишите цикл и назовите инвариант.
3. Проверка палиндрома с пропуском не-букв: где здесь может возникнуть ошибка на единицу?
4. Три числа с нулевой суммой: как избежать повторов в ответе, не используя множество?
5. Сбор дождевой воды двумя указателями: почему достаточно хранить только два максимума?