Что такое 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":
| right | char | Действие | Окно | best |
|---|---|---|---|---|
| 0 | a | добавили | a | 1 |
| 1 | b | добавили | ab | 2 |
| 2 | c | добавили | abc | 3 |
| 3 | b | b уже в окне: убрали a, убрали b, добавили новый b | cb | 3 |
Хотя внутри 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.