Подготовка к алгоритмическим задачам

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

14 мин чтения

алгоритмы

оптимизация

собеседование

Зачем нужна эта техника

Огромный пласт задач звучит одинаково: «найдите самый длинный/короткий подотрезок массива или подстроку, которая удовлетворяет условию». Наивное решение — перебрать все подотрезки. Их O(n²), и для каждого ещё нужно что-то посчитать. На массиве в 100 000 элементов это гарантированный таймаут.

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

На собеседовании эта техника ценится тем, что показывает умение замечать избыточную работу. Интервьюер почти всегда ждёт, что вы начнёте с перебора, а потом сами скажете: «здесь мы пересчитываем одно и то же, давайте двигать окно».

Главная идея на пальцах

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

// Было окно [2, 3, 1], сумма = 6
// Сдвинули вправо: ушла 2, пришла 5
// Новая сумма = 6 - 2 + 5 = 9  ← за O(1), а не за O(k)

Именно эта замена «пересчитать всё» на «вычесть ушедшее, прибавить пришедшее» и даёт выигрыш.

Два вида окна

Техника делится на два случая, и путать их — самая частая ошибка новичков.

Окно фиксированной длины

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

function maxSumOfSize(nums, k) {
  if (nums.length < k) return null;

  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let best = windowSum;

  for (let right = k; right < nums.length; right++) {
    // пришёл nums[right], ушёл nums[right - k]
    windowSum += nums[right] - nums[right - k];
    best = Math.max(best, windowSum);
  }

  return best;
}

maxSumOfSize([2, 1, 5, 1, 3, 2], 3); // 9  → подмассив [5, 1, 3]

Сложность — O(n) по времени и O(1) по памяти. Обратите внимание: индекс уходящего элемента всегда right - k, потому что длина окна не меняется.

Окно переменной длины

Здесь интереснее. Длина заранее неизвестна, вместо неё есть условие: «самая длинная подстрока без повторов», «самый короткий подмассив с суммой не меньше target». Правая граница двигается всегда, левая — только когда условие нарушено.

Общий каркас выглядит так:

let left = 0;

for (let right = 0; right < n; right++) {
  // 1. расширяем окно: учитываем элемент справа
  add(nums[right]);

  // 2. сжимаем окно, пока оно "невалидно"
  while (!isValid()) {
    remove(nums[left]);
    left++;
  }

  // 3. окно валидно — обновляем ответ
  best = Math.max(best, right - left + 1);
}

Этот шаблон стоит выучить наизусть. Девять задач из десяти на скользящее окно укладываются в него, меняются только add, remove и isValid.

Разбор классической задачи

Найдём длину самой длинной подстроки без повторяющихся символов. Строка "abcabcbb" → ответ 3 (подстрока "abc").

Наивный подход

function lengthOfLongestNaive(s) {
  let best = 0;

  for (let i = 0; i < s.length; i++) {
    const seen = new Set();
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break;
      seen.add(s[j]);
      best = Math.max(best, j - i + 1);
    }
  }

  return best;
}

Работает, но O(n²). На строке в 10⁵ символов это порядка 10¹⁰ операций — безнадёжно.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Через скользящее окно

Держим в множестве символы текущего окна. Как только справа приходит дубликат, двигаем левую границу, пока дубликат не уйдёт.

function lengthOfLongest(s) {
  const window = new Set();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    // сжимаем, пока символ s[right] уже есть в окне
    while (window.has(s[right])) {
      window.delete(s[left]);
      left++;
    }

    window.add(s[right]);
    best = Math.max(best, right - left + 1);
  }

  return best;
}

lengthOfLongest('abcabcbb'); // 3
lengthOfLongest('bbbbb');    // 1
lengthOfLongest('pwwkew');   // 3

То же самое на Python:

def length_of_longest(s: str) -> int:
    window = set()
    left = 0
    best = 0

    for right, ch in enumerate(s):
        while ch in window:
            window.discard(s[left])
            left += 1

        window.add(ch)
        best = max(best, right - left + 1)

    return best

Сложность — O(n). Кажется, что вложенный while портит оценку, но это не так: указатель left за всё время работы проходит массив максимум один раз. Суммарно оба указателя делают не больше 2n шагов. Это важный аргумент, который стоит проговорить вслух на собеседовании — интервьюеры часто специально спрашивают: «а почему это не квадрат?».

Когда нужен счётчик, а не множество

Если в окне могут быть повторы и важно их количество, Set не подойдёт — нужна хеш-таблица «символ → сколько раз встречается».

Задача: самая длинная подстрока, в которой можно заменить не более k символов, чтобы все символы стали одинаковыми.

function characterReplacement(s, k) {
  const count = new Map();
  let left = 0;
  let maxFreq = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    count.set(ch, (count.get(ch) || 0) + 1);
    maxFreq = Math.max(maxFreq, count.get(ch));

    // символов на замену больше, чем разрешено
    while (right - left + 1 - maxFreq > k) {
      count.set(s[left], count.get(s[left]) - 1);
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

characterReplacement('AABABBA', 1); // 4

Ключевая строка — right - left + 1 - maxFreq. Это количество символов, которые придётся заменить: длина окна минус самая частая буква в нём.

Типичные ошибки

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

Обновление ответа до сжатия окна. Если посчитать best раньше, чем окно стало валидным, в ответ попадёт невалидный отрезок. Порядок «расширили → сжали → обновили ответ» нарушать нельзя.

Забытое обновление структуры при сдвиге left. Увеличили left, но не удалили элемент из Set или не уменьшили счётчик — состояние окна разъезжается с его границами. Симптом: ответ больше правильного.

Попытка применить технику там, где она не работает. Скользящее окно требует, чтобы условие было «монотонным»: если окно невалидно, его расширение не сделает его валидным. Для массивов с отрицательными числами и условием «сумма ровно X» это не выполняется — там нужны префиксные суммы с хеш-таблицей.

Как распознать задачу на собеседовании

Почти наверняка это скользящее окно, если в условии есть:

слова «подмассив», «подстрока», «непрерывный отрезок»;
требование найти минимум или максимум длины;
ограничение вида «не более k различных символов», «сумма не превышает», «без повторов».

И наоборот: если речь про подпоследовательность (элементы не обязаны идти подряд) — окно не подойдёт, скорее всего это динамическое программирование.

Что запомнить

Скользящее окно превращает перебор всех подотрезков O(n²) в один проход O(n).
Окно фиксированной длины — механическое «добавил справа, убрал слева».
Окно переменной длины — шаблон «расширяем → сжимаем, пока невалидно → обновляем ответ».
Вложенный while не портит сложность: каждый указатель проходит массив максимум один раз.
Для повторов нужен счётчик, а не множество.

Закрепите на практике

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