Обработка массива двумя указателями

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

Идея метода двух указателей

Пусть массив имеет индексы от \(0\) до \(n-1\). Два указателя обычно обозначают \(l\) и \(r\): \(l\) — левая граница текущего отрезка, \(r\) — правая. В каждый момент рассматривается отрезок \([l,r]\). В зависимости от задачи указатели могут двигаться навстречу друг другу, один за другим или независимо расширять и сужать окно.

Главное свойство метода: указатель обычно движется только в одну сторону. Поэтому каждый индекс посещается не более нескольких раз, а время работы часто составляет \(O(n)\) вместо \(O(n^2)\). Перед применением нужно понять, почему после сдвига одного указателя можно безопасно исключить часть вариантов.

• Для непрерывного отрезка указатели задают окно \([l,r]\).
• Для пары в отсортированном массиве указатели ставят в начало и конец.
• Для группировки один указатель обрабатывает позицию, другой хранит границу уже построенной группы.
• Для каждого сдвига нужно доказать, какие варианты больше не могут быть ответом.

Скользящее окно: поиск подходящего отрезка

Скользящее окно применяют, когда условие зависит от всех элементов текущего непрерывного отрезка и его можно поддерживать при добавлении элемента справа и удалении элемента слева. Например, ищут самый длинный отрезок с суммой не больше \(S\), если все элементы массива неотрицательны.

Алгоритм расширяет окно указателем \(r\). Если условие нарушилось, указатель \(l\) двигается вправо, а из суммы удаляются элементы, которые покинули окно. После восстановления условия обновляется ответ.

Для неотрицательных чисел сумма при увеличении \(r\) не уменьшается, а при увеличении \(l\) не возрастает. Именно эта монотонность позволяет не возвращать указатель назад.

1def longest_segment(a, S):
2    left = 0
3    total = 0
4    best = 0
5
6    for right in range(len(a)):
7        total += a[right]
8        while total > S and left <= right:
9            total -= a[left]
10            left += 1
11        best = max(best, right - left + 1)
12
13    return best

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

Пара элементов: указатели навстречу

Если массив отсортирован по возрастанию и нужно найти пару с суммой \(X\), поставим \(l=0\), \(r=n-1\). Рассмотрим сумму \(a_l+a_r\). Если она меньше \(X\), увеличить сумму можно только сдвигом \(l\) вправо: при фиксированном \(r\) все варианты с меньшим левым индексом дают ещё меньшую сумму. Если сумма больше \(X\), сдвигаем \(r\) влево.

Сортировка обычно занимает \(O(n\log n)\), а сам проход двумя указателями — \(O(n)\). Если исходный порядок элементов важен, вместе со значением хранят исходный индекс. Связь сортировки и указателей разобрана на странице «Сортировка и два указателя», а базовый нұсқа поиска пары — на странице поиска пары элементов.

Разобранный пример: максимальный отрезок с ограниченной суммой

Дан массив положительных чисел \([2,1,3,2,1,1,4]\) и число \(S=7\). Требуется найти длину самого длинного непрерывного отрезка, сумма которого не превосходит \(7\).

На шаге с последним элементом важно не остановиться после первого удаления: цикл должен удалять элементы, пока условие не станет истинным. Всего \(r\) прошёл массив один раз, а \(l\) также прошёл его не более бір раза, поэтому сложность равна \(O(n)\).

Группы, границы и два проходящих указателя

Другой нұсқа — разделение массива на группы по условию. Один указатель \(i\) просматривает элементы, а второй \(p\) указывает позицию, куда следует поставить следующий элемент нужной группы. Например, можно переместить все нулевые элементы в начало или все элементы, меньшие порога \(T\), влево.

1def move_less_than_t(a, T):
2    p = 0
3    for i in range(len(a)):
4        if a[i] < T:
5            a[p], a[i] = a[i], a[p]
6            p += 1
7    return a

После обработки первых \(i\) элементов выполняется инвариант: в позициях от \(0\) до \(p-1\) находятся элементы, удовлетворяющие условию, а в позициях от \(p\) до \(i-1\) — уже просмотренные элементы, которые в первую группу не попали. Такой алгоритм работает за \(O(n)\) и использует \(O(1)\) дополнительной памяти.

Если требуется сохранить взаимный порядок элементов внутри групп, простой обмен может его нарушить. Тогда нужен стабильный алгоритм или дополнительный массив; подробнее о выборе подхода см. стабильную сортировку. Для группировки по конкретному значению полезна бет «Группировка по значению», а для условия — «Группировка по признаку».

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

Метод двух указателей не заменяет все алгоритмы для массивов. Для быстрых границ по уже обработанным элементам применяют префиксный минимум немесе префиксный максимум. Для трёх элементов часто фиксируют один индекс, а оставшиеся два ищут методом навстречу; это описано в поиске тройки элементов. Общая схема метода дана на странице «Метод двух указателей».