Метод скользящего окна: от O(n²) к O(n) на Python

Зачем вам метод скользящего окна?

Помните, как на собеседовании вас попросили найти максимальную сумму подмассива длины k? Вы написали два вложенных цикла, и решение работало... пока массив не стал большим. Тогда вы поняли: O(n²) — это медленный путь. Метод скользящего окна — это техника, которая превращает квадратичную сложность в линейную. В этой статье вы разберётесь, как работает окно, увидите код на Python и научитесь применять его к задачам с фиксированным и переменным размером окна.

В чём суть метода скользящего окна?

Представьте, что вы идёте по коридору с фонарём, освещающим ровно k плиток. Вместо того чтобы каждый раз заново зажигать свет, вы просто сдвигаете фонарь на одну плитку: одна плитка гаснет, другая загорается. Обновление происходит за константное время — O(1). Так работает скользящее окно: мы используем уже вычисленную информацию, а не пересчитываем всё с нуля.

Почему это даёт O(n)? Каждый элемент массива участвует максимум в двух операциях: добавлении при расширении окна и вычитании при сужении. Ни один элемент не обрабатывается больше двух раз.

Ключевое условие — непрерывность. Если задача зависит только от непрерывного блока (сумма, произведение, количество уникальных символов и т.д.), мы можем безопасно отбросить левый элемент, когда он больше не может быть частью оптимального окна.

Задача 1: фиксированное окно — максимальная сумма подмассива длины k

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

def max_sum_bruteforce(nums, k):
    best = float('-inf')
    for i in range(len(nums) - k + 1):  # O(n)
        current = 0
        for j in range(i, i + k):       # O(k)
            current += nums[j]
        best = max(best, current)
    return best

Для каждого начального индекса мы пересчитываем сумму k элементов. Когда k близко к n, сложность становится O(n²).

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

def max_sum_sliding(nums, k):
    # Сумма первого окна
    window_sum = sum(nums[:k])
    best = window_sum

    # Сдвигаем окно: убираем левый элемент, добавляем правый
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # O(1) обновление
        best = max(best, window_sum)
    return best

Каждый элемент добавляется один раз (когда входит в окно) и вычитается один раз (когда покидает его). Цикл выполняется n-k раз, итого O(n) времени и O(1) дополнительной памяти.

Ловушка: не забудьте вычесть элемент, который выходит из окна. Если только добавлять новое значение, сумма будет расти и вы получите сумму префикса, а не фиксированного окна.

Задача 2: переменное окно — минимальная длина подмассива с суммой ≥ target

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

def min_subarray_len_bruteforce(nums, target):
    n = len(nums)
    best = n + 1
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total >= target:
                best = min(best, j - i + 1)
                break
    return 0 if best == n + 1 else best

Снова пересчёт сумм для каждого начального индекса — O(n²).

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

def min_subarray_len(nums, target):
    left = 0
    current_sum = 0
    best = len(nums) + 1  # значение-флаг "не найдено"

    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 == len(nums) + 1 else best

Правый указатель движется только вперёд; левый — только когда окно стало слишком большим. Каждый индекс посещается не более двух раз → O(n).

Ловушка: не сдвигайте левый указатель только один раз за итерацию внешнего цикла — вы можете пропустить более короткое окно, которое появится при дальнейшем расширении. Внутренний цикл while гарантирует, что мы сужаем окно, пока условие выполняется.

Почему это важно?

Метод скользящего окна превращает целый класс задач о непрерывных подстроках/подмассивах из пугающих квадратичных в линейные. Когда вы освоите ритм двух указателей — расширяйте, пока не выполнится условие, затем сужайте, пока условие ещё выполняется — вы сможете решать:

• Длина наибольшей подстроки с не более чем k различными символами.
• Минимальная длина подмассива с суммой ≥ target.
• Максимальное количество единиц после замены не более k нулей.
• Количество подмассивов, произведение которых меньше порога.

Все они имеют общий скелет: поддерживаем окно, обновляем агрегат за O(1) и сдвигаем.

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

Прямо сейчас откройте LeetCode и решите задачу Longest Substring Without Repeating Characters (3) с помощью скользящего окна. Используйте два указателя и множество для отслеживания символов. Если застряли — вспомните: правый указатель добавляет новый символ, левый удаляет, пока не исчезнут повторы. Удачи!