Скользящее окно

Скользящее окно (sliding window) — алгоритмический паттерн для задач на подмассивах/подстроках: вместо перебора всех вариантов поддерживается «окно» (диапазон индексов), которое расширяется или сжимается за O(1), давая общую сложность O(n).

Зачем нужно

Задачи «найти подмассив с максимальной суммой», «найти наименьшую подстроку, содержащую все символы» при наивном решении требуют O(n^2) или O(n^3). Скользящее окно решает их за O(n), избегая повторных вычислений за счёт инкрементального обновления агрегата при добавлении/удалении элемента из окна.

Где используется

  • Максимальная/минимальная сумма подмассива длины k
  • Наименьшая подстрока, содержащая все символы другой строки
  • Количество уникальных символов в подстроке
  • Обработка сетевых пакетов в sliding window TCP
  • Анализ временных рядов: скользящие средние

Основной контент

Паттерн 1: Фиксированное окно

// Максимальная сумма подмассива длины k — O(n)
function maxSumFixed(arr, k) {
  if (arr.length < k) return null;

  // Инициализация первого окна
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let maxSum = windowSum;

  // Скольжение: добавляем справа, удаляем слева
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // O(1) обновление
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// maxSumFixed([2, 1, 5, 1, 3, 2], 3) → 9 (5+1+3)

Паттерн 2: Переменное окно

Окно расширяется пока выполняется условие, сужается когда нарушается.

// Минимальная длина подмассива с суммой ≥ target — O(n)
function minSubarrayLen(arr, target) {
  let left = 0, sum = 0, minLen = Infinity;

  for (let right = 0; right < arr.length; right++) {
    sum += arr[right];                  // расширяем окно вправо

    while (sum >= target) {             // условие выполнено
      minLen = Math.min(minLen, right - left + 1);
      sum -= arr[left++];              // сужаем слева
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// minSubarrayLen([2, 3, 1, 2, 4, 3], 7) → 2 ([4,3])

Паттерн 3: Переменное окно с хеш-таблицей

// Длина наибольшей подстроки без повторяющихся символов — O(n)
function longestUniqueSubstr(s) {
  const seen = new Map(); // символ → последний индекс
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (seen.has(ch) && seen.get(ch) >= left) {
      left = seen.get(ch) + 1; // сдвигаем левую границу
    }
    seen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// longestUniqueSubstr("abcabcbb") → 3 ("abc")
// longestUniqueSubstr("pwwkew") → 3 ("wke")

Шаблон выбора

Длина окна фиксирована                → Фиксированное окно
Ищем подмассив/подстроку с условием   → Переменное окно
Нужен учёт частот символов            → Переменное окно + Map/Set
Нужен максимум/минимум в окне         → Deque (monotonic queue)

Частые ошибки

  • Не обновлять левую границу при нарушении условия — окно «накапливает» лишние элементы.
  • Считать размер окна как right - left вместо right - left + 1.
  • Использовать вложенный цикл вместо инкрементального обновления — теряется O(n) сложность.
  • Путать со Два указателя: окно — для непрерывных подмассивов/подстрок, два указателя — для пар элементов.

Связанные темы

Ресурсы