Шаблон скользящего окна: как превратить O(n²) в O(n)

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

Вы когда-нибудь писали два вложенных цикла для поиска подстроки с уникальными символами, а потом смотрели на тайм-аут на LeetCode? Знакомо. Скользящее окно — это шаблон, который превращает O(n²) в O(n) и избавляет от головной боли с индексами. В этой статье вы научитесь применять его к классическим задачам и поймёте, как он работает «под капотом».

Как работает скользящее окно?

Представьте массив как конвейер. У вас есть два указателя: левый (начало окна) и правый (конец окна). Вы двигаете правый указатель вперёд, добавляя новый элемент в текущее состояние (сумму, количество символов и т.д.). Если состояние нарушает условие (например, появился дубликат или сумма превысила цель), вы сдвигаете левый указатель, удаляя элементы, пока условие снова не выполнится.

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

Магия не в сложной структуре данных, а в монотонном движении указателей — они никогда не идут назад. Вы просто поддерживаете окно «здоровым», двигаясь вперёд.

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

Задача LeetCode 3 — классика собеседований.

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

def length_of_longest_substring_bruteforce(s: str) -> int:
    max_len = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break  # нашли дубликат
            seen.add(s[j])
            max_len = max(max_len, j - i + 1)
    return max_len

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

def length_of_longest_substring(s: str) -> int:
    freq = [0] * 128  # для ASCII, O(1) памяти
    left = 0
    max_len = 0
    for right in range(len(s)):
        r_char = s[right]
        freq[ord(r_char)] += 1
        # если появился дубликат, сдвигаем левый указатель
        while freq[ord(r_char)] > 1:
            freq[ord(s[left])] -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

Каждый символ добавляется один раз (правый указатель) и удаляется не более одного раза (левый указатель). Внутренний цикл while выполняется только когда нужно удалить дубликат — общее число операций линейно.

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

Пример 2: Минимальный подмассив с суммой ≥ target

Задача LeetCode 209.

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

def min_sub_array_len_bruteforce(target: int, nums: list[int]) -> int:
    min_len = float('inf')
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total >= target:
                min_len = min(min_len, j - i + 1)
                break
    return min_len if min_len != float('inf') else 0

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

def min_sub_array_len(target: int, nums: list[int]) -> int:
    left = 0
    total = 0
    min_len = float('inf')
    for right in range(len(nums)):
        total += nums[right]
        # пока сумма достаточна, пытаемся уменьшить окно
        while total >= target:
            min_len = min(min_len, right - left + 1)
            total -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0

Правый указатель проходит массив один раз. Каждый раз, заходя в while, мы двигаем левый указатель, и он никогда не возвращается. Каждый индекс посещается не более двух раз (один раз правым, один раз левым).

Типичная ошибка: обновлять min_len после сдвига left. Если вы сначала сдвинете, то потеряете текущий валидный размер окна. Запоминайте ответ до удаления левого элемента.

Почему это меняет всё

Со скользящим окном вы решите целый класс задач:

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

Шаблон универсален: поддерживайте инвариант, расширяйте окно, пока условие не нарушится, затем сжимайте ровно настолько, чтобы восстановить его. Это тренирует мышление в терминах состояния и инкрементальных обновлений — навык, полезный не только на собеседованиях, но и в повседневной работе с логами, временными рядами или коллизиями в играх.

Ваше следующее задание

Закрепите навык: дан массив положительных целых чисел, найдите длину наименьшего непрерывного подмассива, сумма которого равна K. Если такого нет, верните 0. Попробуйте сначала решить скользящим окном, затем — префиксными суммами с хеш-таблицей. Какой подход вам кажется интуитивнее? Напишите своё решение в комментариях!

Держите указатели в движении, и пусть ваши окна всегда будут нужного размера. Удачи в кодинге! 🚀