知识点深化 · 算法 · 双指针与滑动窗口
双指针与滑动窗口：对撞/快慢/窗口模板
双指针是把 O(n²) 暴力优化成 O(n) 的利器：两个指针一前一后、一快一慢或一左一右移动。滑动窗口是其特例，维护一个区间在数组上滑动。这一页把对撞、快慢、窗口三大模板和典型题讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：两个指针如何把嵌套循环压成一次遍历。
2记三种模板（15 分钟）
读④：对撞、快慢、窗口。
3手推例题（20 分钟）
精读⑤。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 区分对撞/快慢/窗口；② 手判回文、有序数组两数之和；③ 写出滑动窗口模板。
② 一图看懂：双指针与滑动窗口全地图
读法：中心是双指针，三种用法并列，下方是典型题与易错。
③ 本质直觉：两个指针代替两层嵌套循环
对撞指针：left 在头、right 在尾，向中间移动。适合有序数组：两数之和、回文判断。比小了 left++，比大了 right--。
快慢指针：两个指针同起点，一快一慢。快的走 2 步慢的走 1 步——判链表有环、找中点、找倒数第 k 个。
滑动窗口：维护一个 [left,right] 区间，right 不断扩展，不满足条件时 left 收缩。求最长/最短满足条件的连续子数组。
为什么能 O(n)暴力是 i 在外 j 在内两层 O(n²)。双指针让每个元素最多被访问常数次，总共一遍 O(n)。
④ 完整体系与对比表
三大模板
| 类型 | 指针位置 | 典型题 |
|---|
| 对撞 | left=0,right=n-1 向中间 | 回文、有序两数之和、盛水最多 |
| 快慢 | 同起点，差速 | 链表环、中点、倒数 k、去重 |
| 滑动窗口 | [left,right] 区间 | 最长无重复子串、和≥target 最短子数组 |
滑动窗口模板
滑动窗口通用模板for(right=0..n){ 加入 arr[right]; while(窗口不满足){ 移出 arr[left]; left++; } 更新答案; }
求最长：扩张时更新答案，不满足才收缩；求最短：满足时就收缩并更新答案。
⑤ 用法场景与典型例题
例1（回文）字符串「abba」用对撞指针判断是否回文
left 头 right 尾向中间比。
① s[0]='a' 对 s[3]='a' 等；② s[1]='b' 对 s[2]='b' 等；③ left≥right 相遇。答案：是回文。
例2（有序两数之和）有序 [1,2,4,6,8,9]，target=10，找两数
对撞，和小左移和大右移。
① 1+9=10 命中！答案：下标 0 和 5。（若 1+9>10 则 right--；<10 则 left++。）
例3（最长无重复子串）字符串「abcabcbb」最长无重复子串长度？
滑动窗口 + 哈希记位置。
窗口扩展遇到重复就收缩 left。最长窗口「abc」长度 3。
做题心法看到"有序数组配对"想对撞；"链表环/中点"想快慢；"最长/最短连续子数组/子串"想滑动窗口。
⑥ 高频错误诊断（4 条）
错误1：无序数组用对撞两数和对撞要求有序。无序用哈希表 O(n)。
错误2：滑动窗口收缩时机错求最长时应在收缩后记录最大长度；求最短时应在满足时就收缩并记录。
错误3：快慢指针步长反判环要 fast 走 2 步 slow 走 1 步，fast 到 null 无环，相遇有环。
错误4：忘了 left 收缩窗口只扩不缩会把所有元素都装进去，永远最长 n，漏掉正确收缩时机。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 对撞 | 有序数组配对/回文 | 比小 left++ 比大 right-- |
| 快慢 | 链表环/中点/倒数 k | fast 2 步 slow 1 步 |
| 滑动窗口 | 最长/最短子串子数组 | 外层扩 right 内层缩 left |
| 复杂度 | 双指针把什么优化 | O(n²)→O(n) |
真题基础1. 判断字符串是否回文，最适合用？
真题中档2. 判断链表是否有环，使用？
真题中档3. 求最长无重复字符子串，使用？
真题拔高4. 有序数组两数之和用对撞指针，当 arr[left]+arr[right] < target 时应？
⑧ 必背知识点卡
对撞：left 头 right 尾向中间 有序数组/回文
快慢：fast 2 步 slow 1 步 环/中点/倒数 k
窗口：right 扩 left 缩 最长最短子数组
有序两数和：和小 left++，和大 right-- O(n)
窗口模板：for right, while 不满足缩 left
优势：把 O(n²) 压成 O(n)
前提：对撞要有序，窗口是连续区间
⑨ 应用输出：求连续子数组和等于 target 的最长长度
场景：给定正数数组，求和等于 target 的最长连续子数组长度。
① 选型：连续区间 → 滑动窗口。
② 扩展：right 遍历，把 arr[right] 加入窗口和 sum。
③ 收缩：当 sum > target 时，移出 arr[left] 并 left++。
④ 命中：sum==target 时记录窗口长度 right−left+1 的最大值。
⑤ 复杂度：左右指针各走一遍 O(n)。
口述思路合上书说："连续子数组问题就套窗口模板，右扩左缩。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础2快慢指针 fast 走几步？
2 步，slow 走 1 步。
基础3滑动窗口维护什么？
一个连续区间 [left,right]。
基础5双指针把几维循环压成几维？
O(n²) 压成 O(n)。
▍中档 6 题
中档7有序两数之和和小了怎么办？
left++。
中档8滑动窗口求最长时何时更新答案？
每次扩张/收缩后记录窗口长度最大值。
中档9为什么无序两数之和不用对撞？
无序无法通过大小判断移动哪边，改用哈希表。
中档10找链表中点快慢指针怎么走？
fast 到尾时 slow 正好在中点。
中档11盛水最多的容器用什么？
对撞：面积=宽×高，短边向内移。
中档12窗口收缩条件一般是什么？
窗口内元素和/计数超阈值或出现重复。
▍拔高 6 题
拔高13最小覆盖子串用什么？
滑动窗口：右扩到覆盖全，左缩到刚好覆盖，记录最短。
拔高14数组去重（原地）快慢怎么做？
slow 记录已去重区末尾，fast 扫描，新值就 slow++ 覆盖。
拔高15三数之和怎么降维？
固定一个 i，对剩余两数用对撞，O(n²)。
拔高16滑动窗口为什么 O(n)？
left 和 right 各自最多移动 n 次，总计 O(n)。
拔高17接雨水用什么双指针？
对撞：左右边走边维护最大高度，接水量=min(左max,右max)-当前高。
拔高18长度最小子数组（和≥s）？
滑动窗口：满足时就收缩左边界并记录最小长度。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 对撞有序夹逼，快慢判环找中点。② 滑动窗口右扩左缩，最长最短子串。③ 双指针把两层循环压一遍 O(n)。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画三种指针示意图 | 能区分用法 |
| 第 2 天 | 背模板 + 基础 1-6 | 移动方向对 |
| 第 3 天 | 做中档 7-12，手推回文 | 对撞过程对 |
| 第 4 天 | 做拔高 13-18，写窗口模板 | 收缩时机对 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写窗口模板 | 不看资料全默对 |
← 返回软件技术总览