Sliding Window (Скользящее окно)
Когда применять:
- Работа с подмассивом или подстрокой (не разрывной частью).
- Нужно найти max/min сумму, длину, или количество уникальных элементов в окне.
- Окно может быть фиксированным (размер k) или динамическим.
Вариант A: Фиксированное окно (Fixed Size)
Задача: Максимальная сумма подмассива длины k.
let maxSum = 0, currSum = 0;
// 1. Инициализируем первое окно
for (let i = 0; i < k; i++) currSum += nums[i];
maxSum = currSum;
// 2. Двигаем окно
for (let i = k; i < nums.length; i++) {
currSum += nums[i] - nums[i - k]; // Добавляем новый, убираем старый
maxSum = Math.max(maxSum, currSum);
}Вариант B: Переменное окно (Dynamic Size)
Задача: Самая длинная подстрока без повторов.
let l = 0, maxLen = 0;
const set = new Set();
for (let r = 0; r < s.length; r++) {
// Пока условие нарушено (дубликат), сжимаем окно слева
while (set.has(s[r])) {
set.delete(s[l]);
l++;
}
// Добавляем новый элемент (расширяем окно)
set.add(s[r]);
maxLen = Math.max(maxLen, r - l + 1);
}