Two pointers и скользящее окно: шаблон и его варианты ТЕМА

О чём статья

Two pointers и sliding window — два близкородственных шаблона, которые часто называют общим термином «два указателя». Они дают линейные алгоритмы там, где наивный подход — квадратичный, и применяются в десятках типов задач: подсчёт пар с условием, поиск кратчайшего/длиннейшего подотрезка с условием, удаление дубликатов, слияние массивов.

Несмотря на близость, у этих шаблонов разные предпосылки и способы движения указателей. Two pointers требует отсортированных (или иначе монотонных) данных и обычно двигает левый и правый указатели «навстречу» или «параллельно». Sliding window работает на исходном (несортированном) массиве и расширяет окно вправо до нарушения инварианта, затем сжимает слева до восстановления. Перепутать эти случаи — частая ошибка, которая ведёт к WA на тестах с особым порядком данных.

---

Когда применять: сигналы в условии

• «Найти пару с условием». Сумма пар, разность пар, отношение — после сортировки решается двумя указателями навстречу за $O(n \log n + n)$.
• «Длиннейший / кратчайший подотрезок со свойством». Если свойство монотонно (расширяем окно — свойство «портится»), подходит sliding window.
• «Сколько подотрезков с условием». Часто работает sliding window с фиксацией правого конца и подсчётом допустимых левых.
• Любое движение по двум массивам параллельно. Слияние, поиск общих элементов в отсортированных массивах.
• Тройные суммы, четверные. Сводятся к фиксации одного-двух элементов и применению two pointers к остатку.

Если ни одно условие не выполняется (свойство не монотонно при движении окна, например), two pointers не работает — нужны другие техники (бинпоиск, DP, структуры данных).

---

Базовый шаблон

Two pointers на отсортированном массиве

Идея в одну фразу: оба указателя двигаются независимо, в зависимости от текущего состояния пары $(a_l, a_r)$.

отсортировать массив a
l ← 0
r ← n - 1
пока l < r:
    если условие(a[l], a[r]) ... :
        l ← l + 1     # либо r ← r - 1
    иначе:
        ...           # обработка совпадения / накопление ответа

Базовая идея: движение происходит в зависимости от того, как сравнивается текущая пара с целью.

Sliding window на любом массиве

Идея в одну фразу: окно $[l, r]$ расширяется вправо, пока инвариант выполнен; при нарушении — сжимается слева до восстановления.

l ← 0
для r от 0 до n - 1:
    добавить a[r] в окно (обновить инвариант)
    пока инвариант нарушен:
        удалить a[l] из окна
        l ← l + 1
    # окно [l, r] валидно, можно обновить ответ

Базовая идея: правый указатель только растёт, левый — тоже только растёт (никогда не возвращается). Это даёт суммарную работу $O(n)$.

Почему оба работают

Two pointers — на отсортированных данных монотонность даёт следующее: если для $l, r$ сумма $a_l + a_r$ слишком велика, то любое движение r влево или l вправо уменьшит сумму. Это позволяет на каждом шаге однозначно сдвинуть один указатель.

Sliding window — суммарная работа линейна, потому что каждый элемент входит в окно ровно один раз (через r) и выходит не более одного раза (через l). Инвариант «свойство монотонно при расширении окна» — обязательное условие. Если расширение может восстанавливать свойство — sliding window не работает.

---

Задача-иллюстрация 1: сумма пар на отсортированном массиве (~CF 1300)

Условие

Дан массив $a_1, \ldots, a_n$ и число $K$. Найти количество пар индексов $(i, j)$, $i < j$, таких что $a_i + a_j = K$.

Ограничения. $1 \le n \le 2 \cdot 10^5$, $|a_i|, |K| \le 10^9$.

Применение шаблона

Сортируем массив. Дальше — классические two pointers: $l = 0$, $r = n - 1$. Сравниваем $a_l + a_r$ с $K$:

• Если $a_l + a_r < K$ — нужна большая сумма, сдвигаем $l$ вправо.
• Если $a_l + a_r > K$ — нужна меньшая сумма, сдвигаем $r$ влево.
• Если $a_l + a_r = K$ — нашли пару. Считаем её и сдвигаем оба, аккуратно учитывая повторяющиеся значения.

Тонкий момент — учёт повторов: если $a_l = a_r$ и в окне $[l, r]$ ещё $m$ одинаковых значений, то пар внутри этого блока $\binom{m}{2}$. Если $a_l \ne a_r$, то пар $\text{cnt}_l \cdot \text{cnt}_r$, где $\text{cnt}_l$ — количество повторов значения $a_l$ слева, $\text{cnt}_r$ — справа.

Код решения

Что поменялось

Базовый шаблон two pointers применяется напрямую, но добавилась обработка повторяющихся значений. Без неё — пропустим пары вида $(a_l, a_{l + 1}, \ldots, a_r)$ при $a_l = a_r$, либо посчитаем их неправильно. Это типичное усложнение шаблона: когда задача спрашивает «количество», а не «существует ли», работа с повторами — отдельная подзадача.

---

Задача-иллюстрация 2: длиннейшее окно без повторов (~CF 1500)

Условие

Дан массив $a_1, \ldots, a_n$. Найти длину длиннейшего подотрезка, в котором все элементы различны.

Ограничения. $1 \le n \le 5 \cdot 10^5$, $1 \le a_i \le 10^9$.

Применение шаблона

Это типичный sliding window. Инвариант — «все элементы в окне различны». При расширении окна вправо инвариант может нарушиться (новый элемент уже был в окне). Тогда сжимаем слева до тех пор, пока повторяющийся элемент не уйдёт.

Поддерживаем set или dict (хешмап) текущих элементов окна — операции добавления и удаления за $O(1)$ в среднем.

Код решения

Что поменялось

Здесь два указателя двигаются в одну сторону (оба слева направо), а не навстречу. Это и отличает sliding window от two pointers на отсортированных данных. Инвариант «уникальные элементы» — монотонный: сжатие окна не может его сломать (удаляем элементы — повторов становится меньше). Это критическое условие применимости sliding window.

Алгоритмическая сложность — $O(n)$ амортизированно: каждый элемент входит в seen один раз и выходит не более одного раза.

---

Задача-иллюстрация 3: минимальное окно с покрытием суммы (~CF 1700)

Условие

Дан массив положительных целых чисел $a_1, \ldots, a_n$ и число $S$. Найти длину кратчайшего подотрезка, сумма которого $\ge S$. Если такого нет — вернуть $0$.

Ограничения. $1 \le n \le 10^5$, $1 \le a_i \le 10^4$, $1 \le S \le 10^9$.

Применение шаблона

«Сумма $\ge S$» — монотонное свойство при расширении окна (массив положительных, сумма только растёт). Подходит sliding window:

1. Расширяем правый указатель, пока сумма $< S$.
2. Как только сумма $\ge S$ — пытаемся сжать окно слева, оставаясь $\ge S$. Сжимаем, пока возможно.
3. Длина текущего окна — кандидат на минимум.

Главное условие — массив положительный. Если есть нули или отрицательные значения, сумма не монотонна, sliding window не работает (нужны префиксные суммы + бинпоиск или другой подход).

Код решения

Что поменялось

Главное отличие от задачи 2: здесь мы хотим минимум, а не максимум, и поэтому обновляем ответ внутри цикла сжатия (а не снаружи). Логика: правый указатель фиксируется, левый сжимает окно как можно сильнее, пока инвариант ещё выполнен; в этот момент текущая длина — кандидат.

В задаче 2 (поиск максимума) обновление было после сжатия — потому что нас интересует самое длинное валидное окно.

Это ключевой нюанс sliding window: где обновлять ответ — внутри цикла сжатия или снаружи — зависит от того, ищем мы минимум или максимум.

---

Типичные ошибки

1. Применение two pointers на несортированных данных. Базовая ошибка. Two pointers (навстречу) требует монотонности; без сортировки решение даёт WA на специально подобранных тестах. Если массив не отсортирован и сортировать нельзя (важен исходный порядок) — это задача на sliding window, а не two pointers.
2. Sliding window на немонотонном свойстве. «Сумма $\le K$ при отрицательных значениях», «среднее значение в окне», «количество различных $= K$ строго» — здесь sliding window даёт WA, потому что свойство не монотонно при движении.
3. Левый указатель сдвигается назад. Признак ошибки: суммарная работа $O(n^2)$ или больше. Если в коде есть l = l - 1 или сброс l = 0 внутри цикла — sliding window не работает, нужен другой алгоритм.
4. Обновление ответа в неверном месте. Для максимума — после полного сжатия (когда окно валидно). Для минимума — внутри сжатия (как только окно валидно, фиксируем длину и пытаемся сжать ещё). Перепутать — WA.
5. Тип под сумму. При $n = 10^5$ и $a_i = 10^9$ сумма до $10^{14}$ — long long в C++. В Python переполнения нет.
6. unordered_set в C++ при анти-хеш-атаках. На Codeforces встречаются специальные тесты против unordered_set<int>. Лекарство — set<int> (логарифм быстрее или сравним на $n \le 10^5$), или ручной хеш с рандомным сидом.
7. Граница < n или <= n. В коде for r in range(n) правый указатель идёт от 0 до $n - 1$; в while l < r указатели не сталкиваются. Часто путают в C++ с диапазонами на основе size_t.

---

Когда НЕ подходит

• Свойство не монотонно при расширении/сжатии окна. Тогда sliding window не помогает; нужны префиксные суммы + хешмап (для «сумма = $K$»), сегментные деревья, или другие структуры.
• Многоразовые запросы по разным окнам. Sliding window работает за один проход; если задача спрашивает «$k$ запросов вида “окно $[l, r]$, дать ответ”» — нужна другая техника (offline-сортировка запросов, sqrt-разбиение, Мо).
• Поиск пары без сортировки и с обязательным порядком индексов. Если порядок важен ($i < j$ и нельзя сортировать), two pointers навстречу не работает; обычно — хешмап «для каждого $a_j$ ищем $K - a_j$ среди уже виденных $a_i$, $i < j$».
• Скользящее окно фиксированной длины + быстрый минимум/максимум. Это «sliding window minimum/maximum» — отдельная задача, решается монотонным деком (см. соседний разбор).

---

Связанные техники

• Бинпоиск по ответу. Когда «найти кратчайший подотрезок со свойством» решается через бинпоиск длины + проверка за $O(n)$. Sliding window часто даёт то же за $O(n)$ напрямую, без бинпоиска.
• Префиксные суммы. Когда свойство «сумма равна $K$» и значения могут быть нулевыми или отрицательными. Sliding window не работает, префикс-суммы + хешмап работают.
• Монотонный дек. Расширение sliding window до «максимум в окне фиксированной длины» или «динамический максимум в растущем окне».
• Three pointers / multiple pointers. В задачах вроде «триплеты с суммой $= K$» — фиксируем один элемент, дальше two pointers на остатке. Сложность $O(n^2)$.

---

Итого

• Техника: two pointers — на отсортированных данных, два указателя двигаются независимо; sliding window — на любых данных с монотонным свойством, оба указателя только растут.
• Сложность шаблона: $O(n)$ после сортировки (если она нужна, $O(n \log n)$).
• Сигналы в условии: «пара с условием», «подотрезок со свойством», «кратчайший/длиннейший с инвариантом».
• Типичные ловушки: применение two pointers без сортировки, sliding window на немонотонном свойстве, движение левого указателя назад, обновление ответа не в том месте цикла сжатия.