Два указателя

Какой самый долгий период в истории Алматы, когда за всё время выпало не больше миллиметра дождя? Дней в ряду 31 046, а отрезков из подряд идущих дней — почти полмиллиарда: перебирать их все долго. Но хватает одного прохода, если завести два индекса — левый и правый край окна — и двигать оба только вперёд. Подвигайте предел и посмотрите, как меняется ответ.

При пределе в 1 мм самый сухой месяц в ряду — с 11 августа по 10 сентября 2022 года, 31 день. Совсем без осадков — 27 дней осенью 1990-го. При 10 мм — 84 дня летом 1944-го. На каждый ответ указатели делают около 62 тысяч шагов, по два на день: правый — когда день входит в окно, левый — когда выходит.

Идея

Если ответ — отрезок или пара индексов, и при сдвиге одного конца другой может двигаться только в одну сторону, то не нужно перебирать все пары концов. Двигаем оба конца вперёд, каждый не больше n раз, и рассматриваем только те пары, которые могут оказаться ответом. Вместо O(n²) получается O(n).

Почему в задаче о засухе так можно? Осадки не бывают отрицательными. Значит, если окно [l, r] не укладывается в предел, то и любое окно [l′, r] с l′ < l тем более не укладывается: в нём те же дни и ещё несколько. Поэтому, когда правый край сдвинулся, левому не нужно возвращаться назад — он только догоняет. Для каждого правого края левый стоит в самом левом допустимом положении, и самое длинное окно с этим правым краем мы видим. Это и называют двумя указателями, а иногда — «гусеницей»: окно ползёт по массиву, вытягивая голову и подтягивая хвост.

Условие важное. Будь в ряду отрицательные числа, сдвиг левого края мог бы увеличить сумму, и правило «левый только догоняет» стало бы неверным. Тогда помогают префиксные суммы с поиском, но уже не за O(n).

Навстречу друг другу: пары с суммой

Вторая разновидность: указатели стоят на двух концах отсортированного массива и идут навстречу. Нужно найти все пары с суммой ровно T. Если a[i] + a[j] меньше T, то a[i] слишком мал даже в паре с самым большим из оставшихся — сдвигаем левый. Если больше — a[j] слишком велик даже с самым маленьким — сдвигаем правый.

Почему пары не теряются, видно на матрице всех сумм. Массив отсортирован, поэтому суммы растут слева направо и сверху вниз, и клетки с суммой ровно T лежат вдоль одной «лестницы» между синим и оранжевым. Каждый шаг указателей вычёркивает целую строку или целый столбец, в котором пары с суммой T уже быть не может, и путь идёт ровно по этой лестнице. За n − 1 шагов он проходит матрицу из n² клеток и не пропускает ни одной нужной.

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

Код

Засуха на всех 85 годах для четырёх пределов и число шагов указателей:

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

Сколько это стоит

Каждый указатель сдвигается не больше n раз, на каждый сдвиг — постоянная работа: O(n) времени и O(1) памяти. Для пар с суммой нужен отсортированный массив, и если он не отсортирован, сортировка добавит O(n log n). Если окно должно помнить, что в нём лежит, — как в задаче о словах без повторов, — добавляется хеш-таблица и O(k) памяти на её содержимое.

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

Где работает

• Слияние. Сортировка слиянием держит по указателю на каждый из двух списков и всегда сдвигает тот, под которым меньше.
• Окна по времени. «Сколько запросов пришло за последние пять минут» — окно, у которого правый край — текущее время, а левый подтягивается за ним. Так работают ограничители частоты и скользящие средние; подробнее — в статье о скользящем окне.
• Пары и тройки. Тройки с нулевой суммой — перебор первого элемента и два указателя по остальным: O(n²) вместо O(n³).
• Сравнение отсортированных списков. Пересечение, разность, поиск общих элементов двух отсортированных таблиц — то же слияние, только с другим действием на каждом шаге. Так базы данных выполняют соединение слиянием.

Задачи

В первой окно должно помнить слова, и на помощь приходит хеш-таблица; тесты — «Война и мир» на русском и английском. Во второй — та же засуха, но для нескольких пределов сразу.