🔶 1. 什么是滑动窗口（Sliding Window）？

滑动窗口是一种使用两个指针维护连续区间的算法技巧。

这个区间会随着指针移动而“滑动”，用来解决数组或字符串中的 连续子区间 问题。

核心思想：

用两个指针（left、right）维护一个满足条件的区间，中间不回头，时间复杂度常为 O(n)

🔶 2. 适用场景

滑动窗口通常用于 “连续子数组 / 子串” 的问题，例如：

✔ 求最长/最短子串

✔ 求满足条件的子数组

✔ 求平均值 / 最大值

✔ 求和为 K 的子区间

✔ 求不包含重复字符的最长区间

✔ 固定长度窗口的处理（最大值、最小值）

如果你看到题目包含以下关键词，大概率是滑动窗口题：

• “连续”
• “子数组 / 子串”
• “最小长度 / 最大长度”
• “满足某条件的区间”

判断标准：一般两个类型的限定条件，a. 元素限定条件（如相等， 出现次数等） b. index区间条件（如：right-left的最大值，right-left满足什么条件等等）

1.  （left, right）区间的"元素组合"满足条件 则(left, right+n)一定满足条件

2. （left, right）区间的"元素组合"不满足条件，则(left+n, right)一定不满足条件

🔶 3. 滑动窗口的基本模型（最通用）

以字符串为例，窗口为 [left, right]：

left = 0
for right in range(len(s)):
    # 1. 扩大窗口，加入 s[right]

    # 2. 满足某些条件时，收缩窗口 left++
    while condition_violated:
        left += 1

    # 3. 在这里统计答案（根据题目不同写法不同）

关键点：

• right 每次向右走一步（扩张窗口）
• left 只在窗口不合法时右移（收缩窗口）
• 整个过程中，left 与 right 都最多走 n 步 → O(n) 时间

🔶 4. 滑动窗口的两大类

✔（1）固定长度窗口

窗口大小固定，例如：

长度为 k 的子数组最大和 股票价格连续 7 天平均值

模板：

window_sum += nums[right]
if right - left + 1 > k:
    window_sum -= nums[left]
    left += 1

特点：

• 不需要 while
• 窗口长度永远为 k

✔（2）可变长度窗口（最经典）

窗口大小不固定，由条件控制。

例如：

最长无重复子串 和至少为 k 的最短子数组 字符频率满足要求的最短覆盖子串

模板就是前面的基本模型。

特点：

• 需要 while 收缩窗口
• 回答通常在收缩/扩张时更新

🔶 5. 最常见的逻辑模式

⭐ 模式 A：窗口内部不能出现某些元素 ⇒ 收缩窗口

（如最长无重复子串）

while char_count[s[right]] > 1:
    shrink left

⭐ 模式 B：窗口内部某些条件满足时 ⇒ 更新答案并收缩窗口

（如最短覆盖子串）

while window_contains_all_needed:
    update_answer
    shrink left

⭐ 模式 C：窗口和 > / < 目标值 ⇒ 收缩窗口

（如最短子数组和 ≥ K）

while window_sum >= K:
    update_answer
    shrink left

🔶 6. 经典例题示例（以“最长无重复子串”为例）

def lengthOfLongestSubstring(s):
    char_count = {}
    left = 0
    ans = 0

    for right in range(len(s)):
        char_count[s[right]] = char_count.get(s[right], 0) + 1

        # 当出现重复字符时，收缩 left
        while char_count[s[right]] > 1:
            char_count[s[left]] -= 1
            left += 1

        ans = max(ans, right - left + 1)

    return ans

这里窗口始终保持“无重复”，并在此基础上求最大长度。

🔶 7. 为什么滑动窗口通常是 O(n)？

因为：

• 左指针最多移动 n 次
• 右指针最多移动 n 次
• 它们都只向右，不回头

因此总时间是 O(n)，远优于暴力 O(n²)。

🔶 8. 什么时候不能用滑动窗口？

滑动窗口不适用于：

• 目标子区间不要求连续
• 需要回溯（如子集、组合、动态规划）
• 区间可以左右跳动，而非单调移动

9. 总结

滑动窗口是双指针技巧，用两个指针维护一个动态可调整的区间，通过不断扩张 right 和按需收缩 left，使窗口在整个数组上线性移动，从而用 O(n) 时间求解各种连续子区间的问题。