滑动窗口（Sliding Window）是一种经典的算法设计技巧，主要用于处理线性数据结构（如数组、字符串、链表）上的连续子序列（子数组或子串）问题。它通过维护一个“窗口”在数据上滑动，避免重复计算，从而将暴力枚举的 O(n²) 或更高复杂度优化至 O(n)
- 窗口：数据中一段连续的区间 left, right（左闭右开）或 left, right。
- 左指针（left）：窗口左侧边界。
- 右指针（right）：窗口右侧边界。
- 滑动过程：
- 先扩展右指针（right++），扩大窗口。
- 当窗口状态不满足条件时，收缩左指针（left++），缩小窗口。
- 每次窗口合法时，记录或更新答案。
算法设计通用模板（以数组为例）
function slidingWindow(arr: number[], target: number): number {
let left = 0;
let maxResult = 0; // 或 minResult、count 等，根据题目
let windowState = 0; // 维护窗口内的某种状态（如和、元素个数、唯一字符等）
for (let right = 0; right < arr.length; right++) {
// 1. 扩展右边界：加入 arr[right]
windowState = updateWhenAdd(windowState, arr[right]);
// 2. 当窗口不合法时，收缩左边界
while (windowInvalid(windowState, target) && left <= right) {
windowState = updateWhenRemove(windowState, arr[left]);
left++;
}
// 3. 此时窗口合法，更新答案
maxResult = Math.max(maxResult, right - left + 1); // 例如求最大长度
}
return maxResult;
}
常见滑动窗口类型
- 固定窗口大小（窗口长度固定为 k）
- 典型问题：求长度为 k 的子数组的最大/最小和、最大平均值等。
- 方法：右指针移动 k 步后开始记录，左指针始终与右指针保持距离 k。
- 示例：LeetCode 209（最小长度子数组和 ≥ target）可变形为固定窗口。
- 可变窗口大小（窗口长度动态变化）
- 最大/最小长度：求满足条件的最长或最短子数组。
- 计数类：统计满足条件的子数组个数。
- 典型问题：
- LeetCode 3：无重复字符的最长子串（窗口内字符唯一）。
- LeetCode 76：最小覆盖子串（窗口包含所有目标字符）。
- LeetCode 424：最多替换 k 个字符后的最长重复字符子串。
设计滑动窗口的关键步骤
- 明确窗口代表什么：窗口内维护的是一段连续子数组/子串。
- 定义窗口的合法状态：例如，和 ≤ target、无重复字符、包含所有所需元素等。
- 维护窗口状态：
- 使用变量（如 sum、count）、哈希表（Map/Set 统计频率或位置）、双指针等。
- 高效更新：添加右元素 O(1)，移除左元素 O(1)。
- 决定何时移动左/右指针：
- 右指针通常在外层 for 循环中单向移动（保证总时间 O(n)）。
- 左指针在内层 while 循环中移动，直到窗口重新合法。
- 记录答案：在窗口合法时更新全局最优解。
适用问题特征：
- 要求连续子数组/子串的极值（最大、最小、个数）。
- 数据具有线性顺序。
- 条件具有单调性（扩大窗口使条件更严格，缩小则更宽松）。