Скользящее окно: как узнать приём в задаче и написать за O(n)

Короткий ответ. Скользящее окно это два индекса, левый и правый. Оба идут по массиву в одну сторону. Между ними лежит отрезок, и мы держим про него счётчик. Правый край расширяет окно, левый сжимает, когда условие нарушено. Так задачи «самый длинный подмассив с условием» решаются за O(n) вместо O(n²). Ниже сигналы, шаблон, код на Python и разбор.

Что такое скользящее окно?

Окно это непрерывный отрезок массива или строки. Его задают два индекса: left и right. Всё, что между ними, лежит внутри окна.

Окно бывает фиксированным: длина задана, и оно просто едет вправо. И бывает переменным: длина меняется по условию. Второй вид встречается чаще и сложнее.

Главное свойство: оба индекса только растут. Каждый элемент входит в окно один раз и выходит один раз. Поэтому весь проход стоит O(n).

По каким словам в задаче узнать скользящее окно?

• «Самая длинная подстрока без повторов».
• «Наименьший подмассив с суммой не меньше k».
• «Максимальная сумма k подряд идущих элементов».
• «Есть ли перестановка строки s внутри строки t».

Общий признак: речь о непрерывном отрезке. У отрезка есть свойство, которое легко обновить при сдвиге края. Если отрезок может быть не непрерывным, окно не подходит.

Как устроен шаблон переменного окна?

• left = 0. Идём right от 0 до n - 1.
• Добавляем элемент right в счётчик.
• Пока условие нарушено, убираем элемент left из счётчика и двигаем left вправо.
• Теперь окно верное. Обновляем ответ его длиной или содержимым.

Внутренний while не делает проход квадратичным. left проходит массив один раз за всю работу.

Как это выглядит на примере?

Строка «abcabcbb», ищем самую длинную подстроку без повторов. right на a, b, c: окно «abc», длина 3. right на второй a: повтор. Двигаем left, пока первая a не выйдет. Окно «bca».

right на второй b: повтор. left уходит за первую b. Окно «cab». right на второй c: окно «abc». right на третьей b: окно «cb». right на последней b: окно «b». Ответ 3.

Как написать скользящее окно на Python?

def longest_unique(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:            # условие нарушено
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

def min_subarray_len(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:      # окно годится, пробуем сжать
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Во второй функции условие «пока годится» вместо «пока нарушено». Так ищут минимальное окно. Логика та же, меняется только знак.

Чем скользящее окно отличается от двух указателей?

Признак	Скользящее окно	Два указателя с концов
Направление	Оба идут вправо	Идут навстречу
Что ищем	Непрерывный отрезок	Пару элементов
Нужна сортировка	Нет	Обычно да
Состояние	Счётчик по окну	Только два значения
Пример	Longest Substring Without Repeating	Two Sum II

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

Как решить Minimum Window Substring?

Дана строка s и строка t. Нужно самое короткое окно в s со всеми буквами t. Кратность букв учитывается.

Считаем буквы t в словаре need. Двигаем right и уменьшаем need по букве. Заводим счётчик missing, сколько букв ещё не хватает. Когда missing равен нулю, окно годится. Сжимаем left, пока окно годится, и запоминаем лучшее.

Каждая буква входит и выходит один раз. Время O(|s| + |t|).

Как решить задачу про максимальную сумму k подряд идущих?

Это фиксированное окно. Считаем сумму первых k элементов. Дальше на каждом шаге прибавляем новый элемент справа и вычитаем ушедший слева. Запоминаем максимум.

Пересчёт суммы с нуля на каждом шаге дал бы O(n · k). Окно даёт O(n). Это самый короткий пример, с которого стоит начинать объяснение.

На каких ошибках ломается скользящее окно?

• Сбрасывают left в ноль при нарушении вместо сдвига на один. Получается O(n²).
• Обновляют ответ до того, как окно снова стало верным.
• Считают длину как right - left вместо right - left + 1.
• Берут окно для задачи про подпоследовательность, где элементы могут не идти подряд.

Как объяснить приём на собеседовании?

Скажите: ответ это непрерывный отрезок, свойство отрезка легко обновить при сдвиге края. Назовите два индекса и счётчик. Назовите время O(n) и объясните: каждый индекс идёт только вправо.

Потом покажите наивное решение за O(n²). Скажите, что окно убирает пересчёт с нуля. Это и есть довод.

Отработать узнавание приёма можно на странице скользящее окно. Версия с фиксированной длиной лежит на странице окно фиксированного размера.

Вопросы и ответы

Работает ли окно с отрицательными числами?

Для задач про сумму нет. Условие «сумма не меньше k» перестаёт быть монотонным. Тогда берут префиксные суммы с хеш-таблицей.

Как хранить счётчик для строк?

Словарь буква в число или массив из 26 ячеек для латиницы. Массив быстрее, словарь универсальнее.

Как понять, что задача про фиксированное окно?

В условии есть число k и слова «подряд идущих». Тогда окно всегда длины k, а left равен right - k + 1.

Что делать, если условие про окно сложное?

Держите вспомогательную структуру. Для «не больше k разных букв» это словарь со счётчиками и его размер. Для «максимум в окне» это монотонная очередь. Само движение краёв не меняется.

Где приём встречается в реальных системах?

В ограничителях запросов: сколько запросов пришло за последнюю минуту. В мониторинге: среднее по последним ста измерениям. Это то же окно, только по времени.