Алгоритмы с нуля

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

Суть Окно [left, right] скользит по массиву. Вместо пересчёта свойства для каждого подмассива (O(n²)), ты скользишь и обновляешь за O(1) за шаг, итого O(n). Два варианта: окно фиксированного размера (длина k) и переменного размера (растёшь/сжимаешь по условию).

◷ 20 min

У тебя есть массив, и нужно найти максимальную сумму любых 5 подряд идущих элементов. Наивный подход: пересчитать сумму каждого окна длины 5 с нуля. Это O(n × 5) = O(n). Но если ты уже знаешь сумму одного окна? Ты можешь убрать левый элемент и добавить новый правый, обновив сумму за O(1). Скользи окно по массиву, обновляя раз за шаг. Итого: O(n) вместо пересчёта. Вот техника скользящего окна.

Цель

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

Идея

Скользящее окно — техника, где контигуозный диапазон [left, right] движется по массиву. Вместо пересчёта свойства (скажем, суммы) для каждого возможного подмассива — что стоит O(n²) или хуже — ты держишь это свойство, скользя окно, и обновляешь его за O(1) за шаг.

Два основных варианта:

1. Окно фиксированного размера (постоянная длина k)

Окно всегда длины k. Начни, вычислив свойство (скажем, сумму) для первых k элементов. Потом скользи:

Убери элемент на позиции left из свойства.
Добавь элемент на позиции left + k к свойству.
Продвинь left на 1.

Повторяй, пока правый край не дойдёт до конца массива.

let left = 0;
let windowSum = sum of arr[0..k-1];
let maxSum = windowSum;

for (let right = k; right < arr.length; right++) {
  // Убери arr[left], добавь arr[right]
  windowSum = windowSum - arr[left] + arr[right];
  maxSum = Math.max(maxSum, windowSum);
  left++;
}

2. Окно переменного размера (растёшь и сжимаешь по условию)

Окно растёт, когда ты двигаешь right вперёд. Когда условие становится ложным (скажем, сумма превышает цель), окно сжимается, и ты двигаешь left вперёд. Продолжай, пока right не дойдёт до конца.

let left = 0;
let windowSum = 0;
let result = /* храни результаты */;

for (let right = 0; right < arr.length; right++) {
  // Расти: добавь arr[right]
  windowSum += arr[right];
  
  // Сжимайся, пока условие нарушено
  while (windowSum > target && left <= right) {
    windowSum -= arr[left];
    left++;
  }
  
  // Обработай валидное окно
  result.push({ left, right, sum: windowSum });
}

Почему это работает:

Наивный подход проверяет каждый возможный подмассив. Для n элементов — O(n²) подмассивов. Пересчитать свойство для каждого — O(n²) или O(n³).

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

Ключевое озарение: состояние инкрементально.

Если знаешь сумму [left, right], сумма [left+1, right] это sum - arr[left]. Сумма [left, right+1] это sum + arr[right+1]. Эти обновления O(1), что позволяет всему алгоритму быть O(n).

Код

Запрограммируем окна фиксированного и переменного размера.

1. Фиксированное: максимальная сумма k подряд идущих элементов

Дан arr = [1, 4, 2, 10, 2, 3, 1, 0, 20] и k = 3, найди максимальную сумму.

function maxSumFixedWindow(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 right = k; right < arr.length; right++) {
    // Убери самый левый, добавь новый самый правый
    windowSum = windowSum - arr[right - k] + arr[right];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

2. Переменное: наименьший подмассив с суммой ≥ цель

Дан arr = [2, 3, 1, 2, 4, 3] и target = 7, найди наименьший подмассив с суммой ≥ 7.

function minSubarrayLength(arr, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;
  
  for (let right = 0; right < arr.length; right++) {
    // Расти: добавь правый элемент
    windowSum += arr[right];
    
    // Сжимайся, пока сумма окна слишком большая и валидная
    while (windowSum >= target && left <= right) {
      // Запиши это валидное окно
      minLength = Math.min(minLength, right - left + 1);
      
      // Сжимайся: убери левый элемент
      windowSum -= arr[left];
      left++;
    }
  }
  
  return minLength === Infinity ? 0 : minLength;
}

Попробуй запустить:

function maxSumFixedWindow(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 right = k; right < arr.length; right++) {
  windowSum = windowSum - arr[right - k] + arr[right];
  maxSum = Math.max(maxSum, windowSum);
}

return maxSum;
}

function minSubarrayLength(arr, target) {
let left = 0;
let windowSum = 0;
let minLength = Infinity;

for (let right = 0; right < arr.length; right++) {
  windowSum += arr[right];
  
  while (windowSum >= target && left <= right) {
    minLength = Math.min(minLength, right - left + 1);
    windowSum -= arr[left];
    left++;
  }
}

return minLength === Infinity ? 0 : minLength;
}

const arr = [1, 4, 2, 10, 2, 3, 1, 0, 20];
console.log("Макс сумма 3 подряд:", maxSumFixedWindow(arr, 3));

const arr2 = [2, 3, 1, 2, 4, 3];
console.log("Мин длина подмассива (сумма >= 7):", minSubarrayLength(arr2, 7));
console.log("Мин длина подмассива (сумма >= 15):", minSubarrayLength(arr2, 15));

Вывод

Пошаговый разбор

Трассируем окно фиксированного размера на [1, 4, 2, 10, 2, 3, 1, 0, 20] с k = 3:


      1
      function maxSumFixedWindow(arr, k) {
    

      2
        let windowSum = arr[0] + arr[1] + arr[2];
    

      3
        let maxSum = windowSum;
    

      4
        for (let right = k; right < arr.length; right++) {
    

      5
          windowSum = windowSum - arr[right - k] + arr[right];
    

      6
          maxSum = Math.max(maxSum, windowSum);
    

      7
        }
    

      8
        return maxSum;
    

      9
      }

Теперь трассируем окно переменного размера на [2, 3, 1, 2, 4, 3] ища сумму ≥ 7:


      1
      function minSubarrayLength(arr, target) {
    

      2
        let left = 0, windowSum = 0, minLength = Infinity;
    

      3
        for (let right = 0; right < arr.length; right++) {
    

      4
          windowSum += arr[right];
    

      5
          while (windowSum >= target && left <= right) {
    

      6
            minLength = Math.min(minLength, right - left + 1);
    

      7
            windowSum -= arr[left];
    

      8
            left++;
    

      9
          }
    

      10
        }
    

      11
        return minLength;
    

      12
      }

Сложность

Окна фиксированного и переменного размера обрабатывают каждый элемент массива максимум дважды (раз при расширении, раз при сжатии или скользе):

Задача	Время	Место	Замечания
Макс сумма k подряд (фиксированное)	O(n)	O(1)	Однопроход, обновление O(1) за шаг
Мин длина подмассива (переменное)	O(n)	O(1)	left и right двигаются максимум n раз итого
Макс строка без повтора	O(n)	O(26) или O(k)	Размер алфавита ограничивает место

Почему O(n), а не O(n²)?

Наивный подход: для каждой начальной позиции left вычисли свойство для всех конечных позиций right. Это O(n²).

Скользящее окно: указатели left и right двигаются максимум n раз каждый (никогда назад, всегда вперёд или стоят). Свойство обновляется за O(1) за движение. Итого: O(n) + O(n) = O(n).

Почему окно никогда не “раскользывается” назад:

В окне переменного размера left никогда не двигается назад. Раз элемент покинул окно, сумма окна уменьшится; нам никогда не нужно его добавлять обратно. Эта монотонность гарантирует, что left и right вместе двигаются максимум 2n раз.

Практика 0 / 5

В окне фиксированного размера длины k, сколько времени требуется обновить сумму окна, когда ты скользишь с позиции i на i+1?

На массиве [1, 2, 3, 4, 5], какова максимальная сумма любых 2 подряд идущих элементов?

В окне переменного размера, почему левый указатель никогда не двигается назад (только вперёд или стоит)?

На массиве [2, 3, 1, 2, 4, 3], какова наименьшая длина окна с суммой ≥ 7?

Какое утверждение лучше всего объясняет, почему скользящее окно сводит O(n²) к O(n)?

Частая ошибка

Забыть сжать окно переменного размера. Если ты расширяешь правый указатель, но никогда не двигаешь левый, ты будешь добавлять элементы вечно и не будешь записывать валидные окна. Для “наименьший подмассив с суммой ≥ цель” ты должен сжимать (двигать left) как только сумма выполнит условие, чтобы записать минимальное окно.

Граничные случаи

Пустой результат. Для окон фиксированного размера, если массив имеет меньше k элементов, нет окна — верни null или пустой результат. Для окон переменного размера, если ни одно окно не выполнит условие (скажем, ни один подмассив с суммой ≥ цель), верни 0 или -1 сигнализируя “не найдено.” Всегда проверь эти граничные случаи перед возвратом.

Проверь себя

Викторина

Почему техника скользящего окна так эффективна для задач вроде 'максимальная сумма k подряд идущих элементов'?

Итог

Скользящее окно движет контигуозный диапазон [left, right] по массиву, обновляя свойство (скажем, сумму) инкрементально по дороге.

Ключевые факты:

Окно фиксированного размера: Окно всегда длины k. Скользи путём удаления самого левого элемента и добавления следующего справа. Обновляй за O(1) за шаг.
Окно переменного размера: Расширь правый край, пока условие не нарушится. Сжимай левый край, пока условие не выполнится. Продолжай, пока right не дойдёт до конца.
Почему O(n)? Свойство окна обновляется за O(1) за шаг (добавить и удалить один элемент). Указатели двигаются максимум n раз каждый (никогда назад). Итого: O(n).
Левый указатель не идёт назад (окно переменного размера). Раз окно валидно и мы начали сжиматься, расширение снова путём движения right только сделает его больше, никогда меньше. left двигается только вперёд.
Инкрементальное состояние — ключ. Если знаешь сумму [left, right], сумма [left+1, right] это sum - arr[left]. Пересчёт не нужен.

Дальше ты исследуешь хеширование (где окно скользит по набору уникальных элементов) и продвинутые техники окна (макс строка без повтора и другие задачи со строками).

Продолжить восхождение ↑Префиксные суммы