Обзор

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

Чаще всего окно задается двумя указателями: left и right. Правый указатель расширяет окно, левый - сужает его, когда условие перестает выполняться или когда мы хотим улучшить ответ.

Идея паттерна

Наивное решение для задач на подмассивы часто перебирает все начала и все концы:

for left in range(n):
  for right in range(left, n):
    пересчитать сумму или частоты

Такой подход имеет сложность O(n²) или хуже (в зависимости от того что мы делаем внутри вложенного цикла). Скользящее окно использует тот факт, что соседние окна отличаются всего одним или несколькими элементами.

Например, если мы знаем сумму окна [left..right], то при сдвиге правой границы достаточно добавить новый элемент. При сдвиге левой - вычесть старый.

Два типа окон

Есть два основных варианта.

Фиксированное окно используется, когда размер окна заранее известен. Например, нужно найти максимальную сумму подмассива длины k. Мы расширяем окно до размера k, обновляем ответ, затем одновременно убираем левый элемент и добавляем правый.

Динамическое окно используется, когда размер нужно подобрать. Например, найти самую длинную подстроку без повторов. Правый указатель расширяет окно, а левый двигается только тогда, когда нарушается условие.

Когда использовать

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

1. В задаче спрашивают про подмассив или подстроку.

2. Нужно найти максимальную или минимальную длину отрезка.

3. Нужно поддерживать сумму, количество или частоты внутри отрезка.

4. Элементы можно добавлять и удалять с краев окна.

5. Границы окна двигаются только вперед.

Итоги

Скользящее окно превращает перебор всех отрезков в управляемое движение двух границ. Главный навык - правильно поддерживать состояние окна и понимать, когда сдвигать левую границу.