滑动窗口算法完全指南（万能通用模板）

📖 目录

1. 什么时候用？（适用场景）

当你遇到题目描述中出现以下关键词时，立刻把"滑动窗口"列入候选名单：

数据结构：数组（Array）、字符串（String）

目标对象：连续子数组（Subarray）、子串（Substring）

问题类型：求 最大/最小 长度、求 满足/不满足 某条件的连续片段

隐含单调性：窗口移动时，条件具有单向变化趋势（例如：全是正数时和会增大；字符计数随移动自然增减）

一句话判断：如果题目在问"在一个线性序列中，连续的一段区间满足某个条件，求这段区间的最值"，90% 是滑动窗口。

⚠️ 反例提醒：如果数组含有负数，求和时窗口扩大的同时总和不一定增加（单调性被破坏），标准滑动窗口会失效。此时需考虑前缀和 + 二分查找或单调队列（详见 6.3）。

2. 为什么这样做？（核心原理）

滑动窗口的本质是利用双指针维护一个动态区间，避免暴力枚举所有子数组。

暴力法：固定左边界，遍历右边界，时间复杂度 O(n^2)。

滑动窗口：左右指针均只单向移动（从不回退）。每个元素最多被加入窗口一次、移出窗口一次，时间复杂度 O(n)。

为什么指针不用回退？
因为当窗口不满足条件时，我们移动左指针缩小窗口。由于左指针之前的元素被排除后，情况只会变得更"差"（对于最长题）或更"好"（对于最短题），所以不存在左指针右移后，又需要回头把刚才丢掉的元素捡回来的场景。这就是 "单调性" 保证的。

3. 怎么做？（万能三段式模板）

将解题过程拆解为三个独立的逻辑原子层：状态定义层、原子动作层、驱动控制层。

3.1 第一阶段：定义状态变量

left = 0                    # 左指针（窗口起始）
state = 0 / dict() / set()  # 维护当前窗口的核心状态（比如和、字符频率、最大频次等）
ans = 0 或 float('inf')     # 最终答案（求最长用0，求最短用无穷大）

3.2 第二阶段：两个原子操作

把"加元素"和"删元素"写成独立逻辑，确保状态绝对正确：

原子操作 A（纳入右边界）：state += nums[right] 或 char_count[ch] += 1

原子操作 B（剔除左边界）：state -= nums[left] 或 char_count[s[left]] -= 1

3.3 第三阶段：驱动控制层（核心代码骨架）

def slidingWindow(nums, 约束条件):
    left = 0
    state = 初始值
    ans = 0 或 inf

    for right in range(len(nums)):
        # ---------- 步骤1：扩张（原子操作 A）----------
        将 nums[right] 纳入 state

        # ---------- 步骤2：收缩（while 循环）----------
        # 安全锁：left <= right 防止越界（推荐加上）
        while left <= right and (窗口违反约束条件):
            # 【情景A】如果是求"最短/最小"，在这里更新答案
            # ans = min(ans, right - left + 1)

            # 原子操作 B：剔除左边界
            state 移除 nums[left]
            left += 1

        # ---------- 步骤3：更新答案 ----------
        # 【情景B】如果是求"最长/最大"，在这里更新答案
        # ans = max(ans, right - left + 1)

    # 注意：求最短时若 ans 未被更新（仍为 inf），题目通常要求返回 0
    return ans if ans != float('inf') else 0

模板工作流（可视化的执行路径）：

flowchart TD
    START(["for right in range(n)"]) --> EXPAND["原子操作 A：纳入 nums[right] 到 state"]
    EXPAND --> WHILE{"while 窗口违反\n约束条件?"}
    
    WHILE -->|是| WHILE_UPDATE["【最短】在此更新 ans\nans = min(ans, 窗口长度)"]
    WHILE_UPDATE --> SHRINK["原子操作 B：剔除 nums[left]\nleft += 1"]
    SHRINK --> WHILE
    
    WHILE -->|否 → 窗口已合法| WHILE_END_UPDATE["【最长】在此更新 ans\nans = max(ans, 窗口长度)"]
    WHILE_END_UPDATE --> LOOP["right += 1，继续下一轮"]
    LOOP --> EXPAND

4. 黄金决策表（最关键！）

while 的条件写什么？ans 更新放在哪里？ 记住这张表即可：

题目类型 代表例题 while 收缩条件（窗口违反了什么？） ans 更新位置
求最长/最大 无重复最长子串（LC 3）
替换后最长重复字符（LC 424）		 窗口 不满足 题意（出现重复 / 替换次数超标） while 循环 之后（此时窗口一定合法）
求最短/最小 和 ≥ target 的最短子数组（LC 209）
最小覆盖子串（LC 76）		 窗口 满足 题意（和 ≥ target / 覆盖了所有字符） while 循环 内部（收缩前刚刚满足，此时是最短候选）

记忆口诀：长在后，短在前 —— 最长答案更新在 while 后面；最短答案更新在 while 前面（内部）。

💡 理解「最短的 while 条件为什么是『满足才收缩』」：
求最短时，我们的目标是找到满足条件的 最短 窗口。当窗口已经满足条件时，我们希望尝试缩小左边界来看看能不能更短。所以 while 的逻辑是「既然已经满足了，那就试试看还能不能更短」—— 每次把左边界往右缩一格，然后检查是否依然满足条件。一旦缩小到不再满足，就停止收缩，继续右移扩张。这正是「记完长度再修烂摊子」的含义：先记录当前这个满足条件的窗口长度，再试图缩小它。

flowchart LR
    Q{"问题类型?"}
    Q -->|求最长/最大| L1["while 条件：窗口不满足题意"]
    Q -->|求最短/最小| S1["while 条件：窗口满足题意"]
    
    L1 --> L2["ans 更新位置：while 循环之后"]
    S1 --> S2["ans 更新位置：while 循环内部"]
    
    L2 --> M["👈 长在后"]
    S2 --> N["👉 短在前"]

5. 实战实例（手把手套用模板）

我们用 LeetCode 209. 长度最小的子数组 来完整演绎一遍。

题目
给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。若不存在，返回 0。

Step 1：套用决策表
求 最短 → 更新答案在 while 内部。

while 收缩条件：窗口 满足 题意（即 cur_sum >= target）。

Step 2：代码实现（带详细注释）

from typing import List

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 1. 状态定义
        left = 0
        cur_sum = 0
        ans = float('inf')  # 最短初始化为无穷大

        # 2. 驱动控制
        for right in range(len(nums)):
            # 原子操作 A：扩张，纳入右边元素
            cur_sum += nums[right]

            # 收缩：当窗口满足条件（和 >= target）时，尝试缩小以寻找更短
            # 加上 left <= right 作为安全锁
            while left <= right and cur_sum >= target:
                # 【最短】更新答案（收缩前窗口刚好满足）
                ans = min(ans, right - left + 1)

                # 原子操作 B：剔除左边元素，试图缩小窗口
                cur_sum -= nums[left]
                left += 1

        # 3. 返回结果（若 ans 未被更新，说明无解）
        return 0 if ans == float('inf') else ans

Step 3：复杂度分析
时间复杂度：O(n)。right 遍历一次，left 最多移动 n 次。

空间复杂度：O(1)，只用了常数个变量。

6. 常见易错点与安全锁

6.1 要不要加 left <= right？

强烈建议默认加上。虽然在正数数组或字符哈希的常规题中，状态本身会隐式阻止左指针越过右指针，但在涉及负数、K次替换、或边界更新顺序写错时，它是防止数组越界的最后一道保险。加上毫无副作用。

6.2 顺序误区（先扩张还是先收缩？）

并不重要。你可以先判断再添加（如你写 LC 3 时的 set 写法），也可以先添加再判断（如 LC 209）。关键是 保证判断条件时，state 变量的状态与窗口区间定义严格一致。

在通用模板中，我们统一采用 "先扩张，后收缩"，因为这样只需维护一套逻辑（while 只负责修复不合法状态），最不容易出错。

6.3 当数组中有负数时怎么办？

标准滑动窗口要求窗口具有"单调性"（扩大一定变差，缩小一定变好）。负数破坏了求和的单调性，此时简单的滑动窗口会失效。

解决方案：使用 前缀和 + 二分查找 或 单调队列（如遇到，属于滑动窗口的进阶变种，模板需微调）。

7. 常见变种与进化方向

前面讨论的都是最经典的双指针动态伸缩模型，滑动窗口还有一些常见变种，值得提前了解：

7.1 固定窗口大小

不是所有滑动窗口都是双指针动态伸缩的。有些题的窗口大小是固定的（比如"长度为 k 的子数组"），此时只需一个 for 循环维护窗口进出，无需 while 收缩。

典型题：LC 643（子数组最大平均数 I）、LC 1343（大小为 K 且平均值大于等于阈值的子数组数目）、LC 1456（定长子串中元音的最大数目）。

7.2 需要辅助数据结构的窗口

当窗口内的"最值"需要实时获取时，简单的哈希或计数器不够用，需要搭配单调队列或堆。

  • 滑动窗口最大值（LC 239）：单调队列（双端队列），O(n) 维护窗口内最大值
  • 滑动窗口中位数（LC 480）：双堆 + 延迟删除，O(n log k) 维护中位数

7.3 双哈希表 + count 变量优化（LC 76 最小覆盖子串 实战）

当窗口的"合法性判断"涉及多个字符的频次比较时，简单的 sum 或单计数器不够用。LC 76 是这个场景的经典题。

套用黄金决策表：
- 求 最短 → ans 更新在 while 内部
- while 收缩条件：窗口 满足 题意（当前窗口已覆盖 t 的所有字符）
- 特殊挑战：判断"是否已覆盖"不能像 LC 209 那样用一个 sum 变量 O(1) 搞定，因为涉及多个字符的频次比较

朴素做法（不推荐）：
每次 while 判断都全量比较两个字典，O(字符集大小)：

# 每次 while 循环都跑一遍，假如 t 有 52 种字符就比 52 次
all(need_dict.get(ch, 0) >= t_dict[ch] for ch in t_dict)

优化：need_dict + count 变量

核心思路是维护一个 count 变量，记录当前窗口中有多少种字符已经达到了 t 的要求。count 只在 刚好达到 或 刚好跌破 门限时变化，不会重复统计。

# ——— 纳入 s[right]（原子操作 A）———
if s[right] in t_dict:
    need_dict[s[right]] = need_dict.get(s[right], 0) + 1
    if need_dict[s[right]] == t_dict[s[right]]:    # 刚好达标
        count += 1

# ——— 剔除 s[left]（原子操作 B）———
if s[left] in t_dict:
    if need_dict[s[left]] == t_dict[s[left]]:      # 刚好从达标变成不达标
        count -= 1
    need_dict[s[left]] -= 1

# ——— while 条件 ———                                           
while left <= right and count == len(t_dict):       # O(1) 判断！

count 状态转换：

stateDiagram-v2
    state "扩张（纳入字符）" as EXPAND
    state "收缩（剔除字符）" as SHRINK
    
    [*] --> EXPAND
    EXPAND --> SHRINK: count == len(t_dict)\n所有字符已达标 → 开始收缩
    SHRINK --> EXPAND: count < len(t_dict)\n某字符跌破门限 → 继续扩张
    note right of SHRINK: 每次收缩前记录最短候选

完整代码（套用万能模板）：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # === 1. 状态定义 ===
        t_dict = {}
        for ch in t:
            t_dict[ch] = t_dict.get(ch, 0) + 1

        left = 0
        need_dict = {}
        count = 0            # 已满足条件的字符种类数
        min_len = len(s) + 1
        ans = ""

        # === 2. 驱动控制 ===
        for right in range(len(s)):
            # --- 扩张（原子操作 A）---
            if s[right] in t_dict:
                need_dict[s[right]] = need_dict.get(s[right], 0) + 1
                if need_dict[s[right]] == t_dict[s[right]]:  # 刚达标
                    count += 1

            # --- 收缩（窗口满足条件时）---
            while left <= right and count == len(t_dict):
                # 【最短】先记长度，再缩小
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    ans = s[left:right + 1]

                # --- 剔除左边界（原子操作 B）---
                if s[left] in t_dict:
                    if need_dict[s[left]] == t_dict[s[left]]:  # 刚跌破
                        count -= 1
                    need_dict[s[left]] -= 1
                left += 1

        return ans

复杂度： O(m + n)，m = len(s), n = len(t)。每个字符至多进出窗口一次。

和万能模板的映射关系：

模板步骤 LC 76 的实现
状态定义 多了 t_dict（目标频次）、need_dict（窗口内频次）、count（达标种类数）
原子操作 A 纳入字符后，仅当 need == target 时 count += 1
while 条件 count == len(t_dict) — 窗口满足题意，即已全覆盖
原子操作 B 剔除字符前，仅当 need == target 时 count -= 1，再减频次
ans 更新位置 while 内部（求最短）

关键洞察： count 的增减时机必须是「刚好跨过门限的那一次」，而不是每次增减都触发。这样既保证正确性，又把判断降为 O(1)。

7.4 前缀和 + 二分查找（数组含负数时的替代方案）

当数组包含负数导致单调性被破坏时，滑动窗口退化为暴力。此时改用前缀和数组（预处理 O(n)），然后枚举每个位置作为左端点，对前缀和数组做二分查找找到满足条件的右端点，时间复杂度 O(n log n)。典型题：LC 560（和为 K 的子数组计数——哈希表优化到 O(n)）。

总结： 80% 的滑动窗口题可以用本文的万能模板解决，剩下 20% 的变种题需要在这个框架上加装特定的数据结构或做算法降级。关键是先判断单调性是否成立。

8. 总结（一句话记住它）

右指针负责闯祸（扩张），左指针负责收拾烂摊子（收缩）。
求最长，先修好烂摊子再记长度；求最短，记完长度再修烂摊子。
加上 left <= right 当保险，这套模板横扫 80% 的滑动窗口题。

如果以后遇到套不进去的变种题（比如含有负数的求和、或需要记录索引的），欢迎随时带着题目回来，我们在这个通用框架上进行特化升级！ 🚀