Метод двух указателей

Метод двух указателей помогает искать отрезки массива, удовлетворяющие условию, не перебирая все пары левой и правой границ. Вместо этого границы отрезка движутся по массиву согласованно, поэтому многие задачи решаются за \(O(n)\) или \(O(n\log n)\) после сортировки.

Идея метода

Отрезок массива задаётся двумя индексами: левой границей \(l\) и правой границей \(r\). Обычно рассматривают отрезок \([l,r]\), включающий оба конца. Если фиксировать \(l\) и перебирать все возможные \(r\), а затем повторять это для каждого \(l\), получится полный перебор массива с квадратичной сложностью \(O(n^2)\). Метод двух указателей позволяет не возвращать указатель назад и рассматривать каждый элемент ограниченное число раз.

Чаще всего указатели называются \(l\) и \(r\). В начале \(l=0\), \(r=0\), текущий отрезок пуст или содержит первый элемент. Указатель \(r\) последовательно увеличивается, добавляя элементы справа. Если условие перестало выполняться, увеличивают \(l\) и удаляют элементы слева, пока условие снова не станет верным.

Главное требование к такому решению — после сдвига левой границы уже не должно быть необходимости проверять отброшенные варианты снова. Это возможно, когда свойство отрезка изменяется предсказуемо: например, сумма неотрицательных элементов при расширении только увеличивается.

Когда метод работает

Классический вариант применяется к массивам неотрицательных чисел. Тогда при добавлении элемента справа сумма отрезка не уменьшается, а при удалении элемента слева — не увеличивается. Благодаря этому, если сумма стала слишком большой, достаточно сдвигать \(l\): уменьшать сумму перебором другого правого конца не нужно.

Типичная задача: найти самый длинный подмассив с суммой не более \(S\). Для неотрицательных чисел поддерживаем условие \(\operatorname{sum}(l,r)\le S\). Расширяем отрезок вправо, а при нарушении условия сдвигаем \(l\) до восстановления допустимости.

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

Алгоритм поиска самого длинного отрезка

Пусть дан массив \(a\) длины \(n\) и число \(S\). Нужно найти длину самого длинного непрерывного отрезка, сумма которого не превышает \(S\). Храним текущую сумму \(sum\), левую границу \(l\) и ответ \(ans\).

1. Установить \(l=0\), \(sum=0\), \(ans=0\).
2. Для каждого \(r\) от \(0\) до \(n-1\) добавить \(a_r\) к \(sum\).
3. Пока \(sum>S\), вычитать \(a_l\) и увеличивать \(l\).
4. После восстановления условия обновить ответ: \(ans=\max(ans,r-l+1)\).

Почему ответ обновляется именно после цикла сдвига \(l\)? Только тогда текущий отрезок снова допустим. Для фиксированного \(r\) выбранная граница \(l\) — самая левая допустимая граница после удаления лишних элементов, значит, этот отрезок имеет максимальную длину среди допустимых отрезков с правым концом \(r\).

1l := 0
2sum := 0
3ans := 0
4for r := 0 to n - 1 do
5    sum := sum + a[r]
6    while sum > S do
7        sum := sum - a[l]
8        l := l + 1
9    ans := max(ans, r - l + 1)

Разобранный пример

Ответ равен \(3\). Например, подходят отрезки \([2,1,3]\), \([1,3,2]\) и \([3,2,1]\) с суммой не более \(6\). Каждый индекс был добавлен в окно один раз и удалён из него не более одного раза, поэтому время работы — \(O(n)\).

Сложность и границы применимости

Хотя внутри внешнего цикла есть цикл while, алгоритм не становится квадратичным. Правая граница \(r\) увеличивается \(n\) раз, а левая граница \(l\) также увеличивается не более \(n\) раз. Значит, суммарное число операций пропорционально \(2n\), то есть сложность равна \(O(n)\), память — \(O(1)\).

Если в массиве есть отрицательные числа, обычное правило может сломаться: удаление отрицательного элемента слева способно увеличить сумму. Тогда движение границ уже не гарантирует восстановление условия. В зависимости от задачи используют префиксные суммы, сортировку, структуру данных или другой вариант обработки массива двумя указателями.

Связь с другими приёмами

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

Если границы фиксированы и нужно быстро считать сумму каждого отрезка, полезны разностный массив или префиксные суммы. Если обработка идёт от правого края, может пригодиться суффиксные суммы. Метод двух указателей не заменяет эти инструменты, а решает другой класс задач — динамическое поддержание одного текущего окна.