re:re:actable
Урок 023 минуты чтения

Что такое sliding window?

На этой странице
Кратко

Sliding window - паттерн для задач на подмассивы и подстроки, где окно двигается по input, а состояние обновляется при добавлении правого и удалении левого элемента. Часто снижает сложность с O(n^2) до O(n).

Вопрос

Что такое sliding window и чем фиксированное окно отличается от переменного?

Fixed-size window

Задача: максимальная сумма подмассива длины k.

function maxSumFixed(nums: number[], k: number): number {
  if (k <= 0 || k > nums.length) return 0 // или null - уточните у интервьюера
 
  let sum = 0
 
  for (let i = 0; i < k; i++) sum += nums[i]
 
  let best = sum
 
  for (let right = k; right < nums.length; right++) {
    sum += nums[right]
    sum -= nums[right - k]
    best = Math.max(best, sum)
  }
 
  return best
}

Вместо того чтобы каждый раз заново складывать k чисел (O(n * k)), мы сдвигаем окно на одну позицию: прибавляем вошедший справа элемент и вычитаем вышедший слева. Пошаговая таблица для этой задачи есть в уроке Как делать dry run.

Variable-size window

Задача: длина самой длинной подстроки без повторов.

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>()
  let left = 0
  let best = 0
 
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left])
      left++
    }
 
    seen.add(s[right])
    best = Math.max(best, right - left + 1)
  }
 
  return best
}

Окно растет вправо, а когда в нем появляется повтор, сжимается слева, пока повтор не исчезнет. Пример s = "abcb":

rightcharДействиеОкноbest
0aдобавилиa1
1bдобавилиab2
2cдобавилиabc3
3bb уже в окне: убрали a, убрали b, добавили новый bcb3

Хотя внутри for есть while, left за всю работу сдвигается не больше n раз, поэтому общая сложность O(n), а не O(n^2).

Когда узнавать паттерн?

  • contiguous subarray;
  • substring;
  • "longest/shortest";
  • "at most K";
  • "without repeating";
  • "sum at least";
  • окно можно расширять и сжимать.

Что отвечать на собеседовании?

Sliding window поддерживает состояние текущего окна [left, right] и двигает границы вместо пересчета каждого подмассива с нуля. Для fixed-size окна размер постоянный, для variable-size окно расширяется и сжимается по условию. Обычно каждый элемент входит и выходит из окна не более одного раза, поэтому time O(n).

Что важно помнить: частые ошибки

  • Применять sliding window к не-contiguous задачам.
  • Забывать удалять левый элемент из состояния.
  • Использовать if вместо while, когда окно нужно сжимать до валидности.
  • Неправильно считать длину right - left + 1.
  • Не обработать k > nums.length.

Мини-шпаргалка

  • Окно = [left, right].
  • Fixed window - размер k.
  • Variable window - сжимается по условию.
  • Каждый элемент обычно входит/выходит один раз.
  • Часто O(n).
  • Состояние: sum, count, Set, Map.

Документация

LeetCode: Sliding Window problems.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам