Скользящее окно в Python: решаем задачи за O(n)

Почему скользящее окно — ваш главный инструмент на собеседовании

Вы когда-нибудь застревали на задаче про самую длинную подстроку без повторяющихся символов? Первое, что приходит в голову — двойной цикл и множество. Но на длинной строке такой подход тормозит. Техника скользящего окна превращает квадратичное решение в линейное. Сегодня вы научитесь применять её на практике.

Суть скользящего окна

Скользящее окно — это способ поддерживать подмассив или подстроку, проходя по данным один раз. Вы двигаете два указателя (левый и правый) и обновляете состояние окна за O(1). Каждый элемент обрабатывается не более двух раз: когда входит в окно и когда выходит. Итоговая сложность — O(n).

Инвариант — ваша путеводная звезда

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

Пример: самая длинная подстрока без повторяющихся символов

Разберём классическую задачу LeetCode.

Наивное решение (O(n²))

def length_of_longest_substring_bruteforce(s: str) -> int:
    n = len(s)
    best = 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

Для строки длиной 10⁵ это будет работать вечность.

Решение со скользящим окном (O(n))

def length_of_longest_substring(s: str) -> int:
    last_seen = {}  # символ -> последний индекс
    left = 0        # начало окна
    best = 0
    for right, ch in enumerate(s):
        # если ch уже есть в окне, сдвигаем левую границу
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Здесь мы просто обновляем словарь и два указателя. Никаких вложенных циклов.

Ещё один пример: минимальная длина подмассива с суммой ≥ target

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

def min_subarray_len(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    best = float('inf')
    for right, val in enumerate(nums):
        current_sum += val  # расширяем окно
        while current_sum >= target:
            best = min(best, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if best == float('inf') else best

Каждый элемент добавляется один раз и удаляется один раз — O(n) времени, O(1) памяти.

Типичные ошибки и как их избежать

• Неправильное обновление left при дубликате: окно может всё ещё содержать дубликат. Используйте left = max(left, last_seen[ch] + 1) или while-цикл.
• Сброс вспомогательных структур внутри внешнего цикла: возвращает O(n²). Держите словарь/сумму живыми, корректируйте только левую границу.
• Игнорирование граничных случаев: пустая строка, все символы одинаковы. Тестируйте на "", "aaaa" и строке из одного символа.

Практический вывод

Скользящее окно — мощный паттерн для задач на подстроки и подмассивы. Потренируйтесь прямо сейчас: возьмите задачу «максимальная сумма подмассива размера k» или «самая длинная подстрока с не более чем двумя различными символами». Напишите инвариант, нарисуйте указатели на бумаге и реализуйте решение. Когда почувствуете, как окно скользит, — вы готовы к собеседованию.