滑动窗口（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;
}

常见滑动窗口类型

1. 固定窗口大小（窗口长度固定为 k）
   • 典型问题：求长度为 k 的子数组的最大/最小和、最大平均值等。
   • 方法：右指针移动 k 步后开始记录，左指针始终与右指针保持距离 k。
   • 示例：LeetCode 209（最小长度子数组和 ≥ target）可变形为固定窗口。
2. 可变窗口大小（窗口长度动态变化）
   • 最大/最小长度：求满足条件的最长或最短子数组。
   • 计数类：统计满足条件的子数组个数。
   • 典型问题：
     • LeetCode 3：无重复字符的最长子串（窗口内字符唯一）。
     • LeetCode 76：最小覆盖子串（窗口包含所有目标字符）。
     • LeetCode 424：最多替换 k 个字符后的最长重复字符子串。

设计滑动窗口的关键步骤

1. 明确窗口代表什么：窗口内维护的是一段连续子数组/子串。
2. 定义窗口的合法状态：例如，和 ≤ target、无重复字符、包含所有所需元素等。
3. 维护窗口状态：
   • 使用变量（如 sum、count）、哈希表（Map/Set 统计频率或位置）、双指针等。
   • 高效更新：添加右元素 O(1)，移除左元素 O(1)。
4. 决定何时移动左/右指针：
   • 右指针通常在外层 for 循环中单向移动（保证总时间 O(n)）。
   • 左指针在内层 while 循环中移动，直到窗口重新合法。
5. 记录答案：在窗口合法时更新全局最优解。

适用问题特征：

• 要求连续子数组/子串的极值（最大、最小、个数）。
• 数据具有线性顺序。
• 条件具有单调性（扩大窗口使条件更严格，缩小则更宽松）。