Что такое sliding window: паттерн скользящего окна

Что такое «скользящее окно» (sliding window)?

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

Подробный ответ

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

Sliding window используют для задач о подмассивах и подстроках. Окно задаётся левой и правой границей. При перемещении границ алгоритм поддерживает нужное состояние, например сумму, частоты символов или количество уникальных значений.

Фиксированный размер окна

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

def max_sum_subarray(items: list[int], k: int) -> int:
    if k <= 0 or k > len(items):
        raise ValueError('Invalid window size')

    current_sum = sum(items[:k])
    maximum = current_sum

    for right in range(k, len(items)):
        current_sum += items[right]
        current_sum -= items[right - k]
        maximum = max(maximum, current_sum)

    return maximum

Динамический размер окна

Иногда размер окна меняется. Например, в задаче «самая длинная подстрока без повторяющихся символов» правую границу расширяют, а левую сдвигают, пока условие окна нарушено.

def longest_unique_substring(value: str) -> int:
    left = 0
    seen = set()
    maximum = 0

    for right, character in enumerate(value):
        while character in seen:
            seen.remove(value[left])
            left += 1

        seen.add(character)
        maximum = max(maximum, right - left + 1)

    return maximum

Когда применять

максимальная или минимальная сумма подмассива;
поиск подстроки с ограничениями;
подсчёт частот элементов в диапазоне;
самая длинная или короткая последовательность, удовлетворяющая условию.

Сложность

В типичных задачах каждый элемент добавляется в окно и удаляется из него не более одного раза. Поэтому временная сложность часто равна O(n), хотя внутри может быть цикл while.

Как ответить на собеседовании

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