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

К сожалению, я не нашел толкового описания метода двух указателей, поэтому напишу свой краткий текст.

Пример

Два указателя — это довольно простая идея, которая нередко встречается в задачах. Давайте сначала рассмотрим пример.

Итак, пусть у нас задача: дан массив из $N$ положительных чисел, надо найти в нем несколько чисел, идущих подряд, так, чтобы их сумма была больше $K$, а чисел в нем содержалось бы как можно меньше.

Первая, довольно понятная идея: пусть мы зафиксировали позицию (номер в массиве) $i$ первого из искомых чисел. Тогда нам надо найти ближайшую к нему справа позицию $j$ такую, что сумма чисел на позициях с $i$ по $j$ больше $K$. Это можно сделать достаточно просто циклом по $j$ от $i$ до $N$, тогда алгоритм решения всей задачи (с учетом перебора $i$) получается следующим:

for i:=1 to n do begin
    s:=0;
    for j:=i to n do begin
        s:=s+a[j]; // в переменной s подсчитываем текущую сумму
        if s>k then begin
            // writeln(j); // этот вывод пригодится дальше
            if j-i+1<min then min:=j-i+1;
            break;
        end;
    end;
end;

Он работает за $O(N^2)$. Придумаем, как его можно ускорить до $O(N)$.

Ключевая идея здесь следующая: если при каком-то $i=i_0$ мы в цикле по $j$ дошли до некоторого значения $j=j_0$, то при следующем $i=i_0+1$ найденное значение $j$ будет обязательно не меньше $j_0$. Говоря по-другому, если мы раскомментируем writeln в приведенном выше коде, то выводимые значения $j$ образуют неубывающую последовательность.

Действительно, если при некотором $i=i_0$ мы пропустили все $j$ до $j_0$, то это значит, что сумма чисел начиная от $i_0$ до всех промежуточных $j$ была $\leq K$. Но тогда если мы начнем считать сумму чисел начиная с позиции $i_0+1$, то для всех тех же промежуточных $j$ сумма чисел уж точно будет $\leq K$ (т.к. по условию все числа положительны).

А это обозначает, что нам не надо каждый раз заново запускать поиск $j$ начиная от $i$! Мы можем каждый раз начинать поиск $j$ с того значения, на котором остановились в прошлый раз:

s:=0;
for i:=1 to n do begin
    for j:=j to n do begin // цикл начинается с j!
        s:=s+a[j]; 
        if s>k then begin
            if j-i+1<min then min:=j-i+1;
            s:=s-a[j]; // это грубый костыль, потому что на следующей итерации
                       // мы будем делать опять s:=s+a[j] с тем же j.
                       // ниже будет видно, как это сделать красивее.
            break;
        end;
    end;
    s:=s-a[i]; // чтобы не вычислять s каждый раз заново
end;

j:=1;
s:=0;
for i:=1 to n do begin
    while (j<n)and(s<=k) do begin // мы таким образом начинаем со старого значения j
        s:=s+a[j];
        inc(j);
    end;
    if s>k then begin
        // +1 пропало, потому что теперь j указывает на первый невзятый элемент.
        if j-i<min then min:=j-i;
    end else // если мы попали сюда, то j=n, но s<=k - дальше искать нечего
        break;
    s:=s-a[i]; // перед началом следующей итерации выкинем число i
end;

Это решение работает за $O(N)$. Действительно, обе переменных цикла — и $i$, и $j$ — все время работы программы только увеличиваются. Общее количество итераций внутреннего цикла будет равно общему количеству увеличений $j$, а это равно $N$. Все, кроме внутреннего цикла, тоже работает за $O(N)$, получаем и общую сложность $O(N)$.

Переменные $i$ и $j$ в даннном контексте часто называют указателями — конечно, не в том смысле, что они имеют тип pointer (что неверно), а просто в том смысле, что они указывают на определенные позиции в массиве. Поэтому и метод этот называется методом двух указателей.

Общая идея

На этом примере очень хорошо видна суть метода двух указателей: мы пользуемся тем, что при увеличении значения одного указателя значение другого указателя тоже может только увеличиваться. Если мы перебираем $i$ в порядке возрастания, то $j$ тоже будет только возрастать — поэтому не надо перебирать каждый раз заново, можно просто продолжать с предыдущего значения.

Конечно, это так не в каждой задаче, но есть задачи, где это можно доказать и это работает.

Еще примеры:

• На прямой находятся $N$ точек; требуется подсчитать количество пар точек, расстояние между которыми $\geq D$. Решение: сортируем точки по координате (если они не отсортированы во входных данных). Идем одним указателем $i$ от 1 до $N$, второй указатель $j$ меняем так, чтобы среди точек, лежащих "правее" $i$ (т.е. с бОльшими номерами) он указывал на самую "левую" точку такую, что расстояние от точки $i$ до точки $j$ было $\geq D$. На каждом шагу добавляем к ответу $N-j+1$ — это общее количество точек, лежащих правее $i$ на расстоянии как минимум $D$ от нее. Поскольку при увеличении $i$ значение $j$ тоже может только увеличиваться, то метод двух указателей сработает.
• Даны два отсортированных массива, надо проверить, есть ли среди них одинаковые числа. Решение: запускаем два указателя, первый ($i$) бежит по одном массиву ($a$), второй ($j$) по другому ($b$) так, чтобы $b[j]$ всегда было первым элементом, большим или равным $a[i]$.
• На окружности заданы $N$ точек, надо найти пару точек, расстояние между которыми (по хорде окружности) максимально. Решение: сортируем точки так, чтобы они шли в порядке обхода окружности, пусть против часовой стрелки. Берем первую точку ($i=1$) и находим максимально удаленнную от нее, пусть это будет точка $j$. Далее переходим к следующей точке против часовой стрелки ($i=2$). Несложно видеть, что самая удаленная от нее точка тоже сдвинется против часовой стрелки (ну или останется на месте), т.е. $j$ только увеличится. И так далее; надо только учесть, что окружность зациклена и после $N$-й точки идет первая. В итоге в решении оба указателя совершат полный оборот по окружности.
• На окружности заданы $N$ точек, надо найти три точки такие, что площадь натянутого на них треугольника максимальна. Решение за $O(N^2$): сортируем точки так же. Зафиксируем первую вершину треугольника. Запустим два указателя для второй и третьей вершин треугольника: при сдвиге второй вершины треугольника против часовой стрелки третья тоже двигается против часовой стрелки. Так за $O(N)$ найдем треугольник максимальной площади при фиксированной первой вершине. Перебрав все первые вершины, за $O(N^2)$ решим задачу.

Альтернативные реализации

Выше у нас всегда один указатель был "главным", а другой "ведомым". Нередко программу можно написать и так, что оба указателя будут равноправными. Ключевая идея — на каждом шагу смотрим на текущую "ситуацию" и в зависимости от нее двигаем один из двух указателей.

Например, в нашем примере про сумму на подотрезке больше $K$:

i:=1;
j:=1;
s:=a[1];
while j<=n do begin
    if s>k then begin
                // если s>k, то надо, во-первых, проверить решение,
                // а во-вторых, точно можно двигать первый указатель
        if j-i+1<min then min:=j-i+1;
        s:=s-a[i]; // не забываем корректировать сумму
        inc(i);
    end else begin // а иначе надо двигать второй указатель
        inc(j);
        s:=s+a[j];
    end;
end;

Еще проще — в задаче поиска двух одинаковых элементов в двух отсортированных массивах (считаем, что массивы отсортированы по возрастанию):

while (i<=n)and(j<=m) do begin
    if a[i]=b[j] then begin
        writeln(i,' ',j);
        break;
    end else if a[i]>b[j] then inc(j)
    else inc(i);
end;

Два указателя и бинпоиск

Многие задачи, решаемые двумя указателями, можно решить и бинпоиском ценой дополнительного $\log N$ в сложности решения. Например, в нашем основном примере можно было бы не двигать второй указатель, а каждый раз его находить заново бинпоиском — правда, пришлось бы заранее посчитать префиксные суммы (т.е. для каждого $k$ вычислить $s[k]$ — сумму первых $k$ элементов массива); после этого сумма на отрезке от $i$ до $j$ вычисляется как разность $s[j]-s[i-1]$.

Аналогично, в задаче поиска двух одинаковых элементов в двух массивах тоже можно написать бинпоиск для поиска нужного $j$.

Но задачу про две наиболее удаленные точки на окружности бинпоиском не очень решишь (хотя можно там сделать тернарный поиск).

Два указателя и сортировка событий или сканлайн

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

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

Много указателей

Бывают задачи, когда вам нужны много указателей. Если вы можете организовать алгоритм так, что все ваши $M$ указателей только увеличивают свои значения, то алгоритм будет работать за $O(NM)$. Как-то примерно так:

while все указатели не дошли до конца do begin
   if можно увеличить первый указатель then увеличить первый указатель
   else if можно увеличить второй указатель then увеличить второй указатель
   else ...
end;