算法与AI · 知识点深化 · 算法思想
滑动窗口进阶：变长窗口、哈希计数、最小覆盖子串
滑动窗口是 O(n) 神器：右指针扩窗口，左指针缩窗口。第一轮学了固定窗口，第二轮攻变长窗口和最小覆盖子串。这一页把窗口模板背熟。
① 怎么学（4 步走，约 65 分钟）
先建立直觉再抠细节，按这四步走最稳：
1看图建立直觉（10 分钟）
读②③：先在脑子里画出本课核心结构图。
2记完整体系（15 分钟）
读④：把对比表和公式看懂，不要急着背。
3跟例题走一遍（20 分钟）
精读⑤：看三个例题怎么用知识点解题。
4刷题纠错（剩余时间）
做⑦⑩，错题回⑥诊断。
本课小目标学完你要能：① 写滑动窗口模板；② 判断什么时候缩左；③ 解最小覆盖子串；④ 无重复最长子串。
② 一图看懂：滑动窗口全景
读法：中心是本课主题，四条分支展开核心维度，下方是典型应用与高频易错点。
③ 本质直觉：滑动窗口就是"伸缩窗口"
一个窗口 [left, right] 在数组/字符串上滑动。right 往右扩，遇到不满足条件的场景 left 往右缩。
模板：right 遍历→加入窗口→while(需要收缩)→更新答案→left++。
关键：想清楚窗口里要维护什么状态（计数、和、哈希），以及什么时候该缩。
什么时候用滑动窗口子串/子数组问题，且 O(n^2) 暴力能优化成 O(n)。定长窗口直接固定宽度；变长窗口伸缩。
④ 完整知识体系
经典题套路
| 题目 | 窗口维护 | 收缩条件 |
|---|
| 无重复最长子串 | Set/Map 字符位置 | 有重复就缩 |
| 最小覆盖子串 | 计数匹配 target | 满足时缩求最小 |
| 长度最小子数组和 | 窗口和 | 和>=target 时缩 |
| 字符串排列 | 计数匹配 | 长度==len 时判断 |
模板for right: 加入; while(需收缩): 更新答案; left++
最小覆盖need 计数, match 计数满足 need 时缩
最小覆盖子串
need 记 target 每个字符需要几个。窗口里维护 window。match 记录已满足的字符种类数。match==need.size 时尝试缩 left 求最小。
⑤ 应用场景与例题
例1 无重复最长子串 abcabcbb
right 扩，字符在窗口里重复就 left 缩到上次出现位置+1。最长 3（abc）。
例2 最小覆盖子串 ADOBECODEBANC, ABC
窗口扩到包含 ABC，缩 left 求最小。答案 BANC。
例3 和>=s 的最小子数组 [2,3,1,2,4,3], s=7
窗口和>=7 时缩 left 求最小长度。答案 [4,3] 长度2。
做题心法扩 right，满足条件时缩 left 求最优，记答案。
⑥ 高频错误诊断（4 条）
错误1：用 O(n^2) 暴力子串问题优先滑动窗口 O(n)。
错误2：收缩时机想反该缩不缩，不该缩乱缩。
错误3：最小覆盖 match 数算错要等种类数都满足才算。
错误4：答案更新位置错在收缩过程中每缩一步都更新最小。
⑦ 考点真题演练（5 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 模板 | 问什么时候缩 | 满足条件/违反条件 |
| 无重复 | 问用什么 | Map 记位置 |
| 最小覆盖 | 问 match 含义 | 已满足字符种类 |
| 复杂度 | 问为什么 O(n) | 左右指针各走 n |
真题basic1. 滑动窗口的时间复杂度？
真题mid2. 无重复最长子串用什么记录字符位置？
真题mid3. 最小覆盖子串中 match 表示？
真题hard4. 为什么滑动窗口是 O(n)？
真题hard5. 长度最小子数组和>=s，什么时候缩 left？
⑧ 必背知识点卡
模板：right 扩，满足缩 left，记答案
无重复：Map 记位置，重复就缩
最小覆盖：need/window match 种类
最小子数组：和>=target 缩
排列：固定长度窗口计数对比
复杂度：左右指针各 O(n)
关键：想清楚收缩条件
⑨ 动手输出：解最小覆盖子串
场景：s 里找包含 t 所有字符的最小子串。
① 初始化：need 记 t 字符计数。
② right 扩：把 s[right] 加入 window。
③ match：窗口字符数满足 need 就 match++。
④ 缩 left：match 满足时缩 left 求最小长度。
⑤ 记录：每缩一步更新最小答案。
口述思路扩到满足，缩到最小，窗口模板通杀。
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础1滑动窗口用几个指针？
两个 left/right。
基础4最小覆盖要维护什么？
need 和 window 计数。
基础5什么时候缩 left？
满足条件或违反条件。
基础6固定窗口怎么写？
right-left+1==k 时缩。
▍中档 5 题
中档1为什么是 O(n)？
左右指针各最多走 n 次。
中档2最小覆盖 match 什么时候加？
窗口字符数达到 need。
中档3无重复最长子串答案？
abcabcbb 是 3。
中档4排列题怎么判断？
窗口长度等于 p.length 时计数对比。
▍拔高 5 题
拔高2替换 K 次最长重复子串？
窗口内其他字符数<=k 时扩。
拔高3至多 K 个不同字符最长子串？
不同字符数>k 时缩。
拔高5最小覆盖为什么要在缩时更新？
缩的时候才可能更小。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① right 扩 left 缩，答案在收缩时更新。② 无重复 Map 位置，最小覆盖 match 种类。③ 左右各走 n，O(n) 通杀子串题。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③，背滑动窗口模板 | 五步写对 |
| 第 2 天 | 背题型表 + 基础 6 题 | 条件记住 |
| 第 3 天 | 做中档 5 题，写无重复子串 | 代码对 |
| 第 4 天 | 做拔高 5 题，写最小覆盖 | match 逻辑 |
| 第 5 天 | 做⑦真题 5 题 | 限时每题 5 分钟 |
| 第 6-7 天 | 合书白板写模板 | 不看资料 |
← 返回算法与AI总览