Два указателя в отсортированном массиве

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

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

Пусть дан массив \(a\), элементы которого расположены по неубыванию: \(a_0 \le a_1 \le \dots \le a_{n-1}\). Два указателя — это обычно два индекса: левый \(l\) и правый \(r\). Они обозначают границы рассматриваемого участка или двух элементов массива.

В задачах на пару указатели стоят на концах массива: \(l=0\), \(r=n-1\). Рассматривается сумма \(a_l+a_r\). В задачах на отрезок они задают окно \([l,r]\), внутри которого поддерживается условие, например ограничение на сумму.

Поиск пары с заданной суммой

Требуется найти два различных элемента, сумма которых равна \(S\). Сначала берём крайние элементы. Если сумма слишком мала, нужно увеличить её: в отсортированном массиве это можно сделать только увеличением \(l\). Если сумма слишком велика, уменьшаем её уменьшением \(r\).

Почему нельзя потерять решение? Если \(a_l+a_r<S\), то для текущего \(l\) любой индекс справа от \(r\) даст сумму не меньше, а при движении вправо сумма не уменьшится. Значит, текущий \(l\) с любым индексом правее \(r\) не подходит, и его можно исключить. Аналогично при слишком большой сумме исключается текущий \(r\).

1def find_pair(a, target):
2    left = 0
3    right = len(a) - 1
4    while left < right:
5        current = a[left] + a[right]
6        if current == target:
7            return left, right
8        if current < target:
9            left += 1
10        else:
11            right -= 1
12    return None

Ответ: пара найдена — элементы \(3\) и \(11\), их индексы \(1\) и \(5\) при нумерации с нуля. Алгоритм сделал только два сравнения, хотя полный перебор проверял бы все пары.

Поиск отрезка с ограничением

Другой вариант — поиск непрерывного отрезка, например самого длинного отрезка с суммой не больше \(K\). Здесь \([l,r]\) называют скользящим окном. Метод особенно удобен, если все элементы массива неотрицательны.

Алгоритм: правый указатель последовательно проходит массив. Каждый новый элемент прибавляется к текущей сумме. Пока сумма больше \(K\), из окна удаляется элемент \(a_l\), а \(l\) увеличивается. После этого обновляется ответ, например длина окна \(r-l+1\).

left := 0
sum := 0
answer := 0
for right := 0..n-1 do
    sum := sum + a[right]
    while sum > K do
        sum := sum - a[left]
        left := left + 1
    answer := max(answer, right - left + 1)

Каждый элемент сначала один раз добавляется в окно, а затем не более одного раза удаляется из него. Значит, несмотря на вложенный цикл while, время работы равно \(O(n)\), а не \(O(n^2)\).

Строки и два указателя

Та же идея применяется к строкам. Например, можно сравнивать строку слева направо, используя индексы \(i\) и \(j\), искать совпадающие символы или проверять, является ли последовательность подстрокой. Для работы с отдельными символами важно понимать, что такое индекс символа, а последовательный просмотр выполняется методом перебора строки.

В задачах на две строки указатели обычно начинают с нулевых индексов. Если символы равны, оба указателя сдвигаются. Если один символ меньше или больше другого, сдвигается указатель в соответствии с условием задачи. Для подсчёта количества символов чаще подходит словарь частот, а не два указателя.

Сложность и условия применимости

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

Для скользящего окна условие монотонности особенно важно. Если в массиве есть отрицательные числа, добавление элемента справа может уменьшить сумму, а удаление слева — увеличить её. Простое правило «сдвигать левую границу, пока сумма велика» тогда может быть неверным. В таких задачах используют другие методы: префиксные суммы, словари или специальные структуры данных.

Алгоритм решения задания

1. Проверьте, отсортирован ли массив. Если нет — выясните, разрешена ли сортировка и не требуется ли сохранить исходные индексы.
2. Определите, что обозначают указатели: два элемента или границы окна.
3. Запишите величину, которую сравниваете с целью: сумму, разность, длину или другое условие.
4. Докажите направление движения: какой указатель изменяет величину в нужную сторону.
5. Укажите границу цикла: обычно \(l<r\) для пары или \(r<n\) для окна.
6. Проверьте крайние случаи: пустой массив, один элемент, отсутствие ответа, повторяющиеся значения.