双指针有哪几类？对撞指针、快慢指针、滑动窗口分别解决什么问题？
简化版
双指针是「用两个指针配合遍历」来把很多 O(n²) 的问题降到 O(n) 的技巧,分三大类:对撞指针(左右指针相向而行,用于有序数组的两数之和、反转、盛水);快慢指针(同向不同速,用于原地修改数组、链表找环/中点);滑动窗口(同向双指针维护一个区间,用于连续子串/子数组问题)。核心思想都是「用指针的移动代替嵌套循环,让每个元素只被访问常数次」。
详细版
| 类型 | 指针关系 | 典型问题 |
|---|---|---|
| 对撞指针 | 左右两端相向移动 | 有序数组两数之和、反转数组/字符串、三数之和、盛最多水的容器、回文判断 |
| 快慢指针 | 同向,一快一慢 | 原地移除元素/去重/移动零、链表判环(Floyd)、链表找中点 |
| 滑动窗口 | 同向,右扩左缩,维护区间 | 无重复最长子串、最小覆盖子串、长度最小子数组、定长窗口 |
共同本质:两个指针各自最多把数组走一遍,总移动 O(n),所以把「枚举所有对/所有子区间」的 O(n²) 优化成 O(n)。
完整版教学
一、双指针到底优化了什么
很多问题的暴力解法是两层循环枚举——枚举所有元素对(O(n²))、枚举所有子区间(O(n²) 甚至 O(n³))。双指针的核心洞察是:利用问题的某种单调性/有序性,让两个指针朝着确定的方向移动,避免重复枚举。因为每个指针最多走一遍数组、不回头,总的移动次数是 O(n),于是把 O(n²) 压到了 O(n)。理解双指针,关键是理解「为什么指针可以只朝一个方向走而不遗漏答案」。
二、对撞指针:利用有序性,两端夹逼
对撞指针从数组两端出发、相向移动,每一步根据当前两个指针的情况决定「移动左还是移动右」。它最典型的应用是有序数组的两数之和:
left在头、right在尾,看a[left] + a[right]。- 和太小 → 需要更大的数 →
left++(左指针右移,值变大)。 - 和太大 → 需要更小的数 →
right--(右指针左移,值变小)。 - 相等就找到。
关键是有序性保证了「移动方向和值的变化方向一致」,所以每次能明确排除一种可能,不会遗漏。反转数组、三数之和(排序后)、盛水容器都是这个套路的变体。
三、快慢指针:读写分离,原地处理
快慢指针同向移动、速度不同。在数组上,它常表现为「读写双指针」:slow 指向「下一个要写入的位置」,fast 负责向前扫描筛选。凡是原地修改数组(移除某元素、去重、移动零)都是它:fast 遇到要保留的元素就写到 slow 处、slow++;要丢弃的就跳过。这样一趟 O(n) 就能原地重排,不需要额外数组。
在链表上,快慢指针指「一次走一步 vs 一次走两步」,用于判环(Floyd)、找中点(详见链表专题)。
四、滑动窗口:维护一个动态区间
滑动窗口是双指针的「区间版」:两个指针 left、right 圈定一个窗口 [left, right],right 不断向右扩展窗口、left 在需要时收缩窗口,始终维护窗口满足某个条件。它专治连续子串/子数组问题:
- 求最长:right 扩展,窗口不合法时 left 收缩到合法,记录最大长度。
- 求最短/最小:right 扩展到窗口合法,然后 left 收缩求最短。
因为 left、right 都只朝右走、各走一遍,滑动窗口是 O(n),把「枚举所有子区间」的 O(n²) 优化掉。
五、如何识别该用哪一类
- 有序数组 + 找两个数满足某和/差 → 对撞指针。
- 原地修改数组(删/去重/移零)、链表找环/中点 → 快慢指针。
- 连续子串/子数组 + 求最长/最短/是否存在满足条件的窗口 → 滑动窗口。
- 看到「排序后能不能双指针」也是常见思路(三数之和、盛水)。
一句话:「有序两端夹」用对撞,「原地筛选」用快慢,「连续区间」用滑窗。
六、双指针的正确性来自「不遗漏」
用双指针最需要论证的是「这样移动为什么不会漏掉答案」。以对撞指针的两数之和为例:当 a[left]+a[right] < target 时,a[left] 和任何比 a[right] 小的数相加都更小,所以 a[left] 不可能再和 right 左边的任何数凑成 target——可以安全地 left++,排除掉 a[left] 这一整行。正是这种「移动一步就排除一批」的性质,保证了双指针不重不漏。写双指针时想清楚这个,才不会出错。
七、把不变量、推演与工程边界落到代码上
算法正确性的核心不是记住某个 while，而是始终维护这个不变量：指针移动必须一次排除一批不可能状态，并保证被丢弃状态不含答案。
对应的状态推进是：对撞利用有序性，快慢指针做读写分离，滑窗维护连续区间状态。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。
初始化边界与状态
while 尚未结束:
根据当前状态作出唯一可证明安全的选择
更新边界、计数或局部结构
断言不变量仍然成立
返回不变量在终止状态下推出的答案复杂度不能只背一个符号。当每个指针单调前进时，总移动次数通常 O(n)。
带数字走一遍：两数之和从 n² 对枚举降为左右合计最多 n 次移动。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。
| 核对项 | 结论 |
|---|---|
| 前提 | 需要有序性、单调性或可增量维护的窗口条件之一 |
| 时间复杂度 | 常见 O(n) |
| 额外空间 | 常见 O(1) 或窗口状态空间 |
| 关键边界 | 若移动后仍无法证明排除安全，就不能仅凭“连续区间”使用双指针 |
| 替代方案 | 哈希、前缀和、二分和单调队列解决不同结构 |
易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。
实现完成后至少检查五类用例：
- 空输入或题目允许的最小规模，验证初始化不会越界。
- 单元素与两个元素，验证循环条件和最后一次推进。
- 大量重复值，验证相等分支、稳定性或去重语义。
- 已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
- 上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。
八、常见误区与追问
- 误区：只要记住模板就适用于所有输入。 本题成立的前提是“需要有序性、单调性或可增量维护的窗口条件之一”，前提被破坏后必须换算法或重新证明。
- 误区：复杂度只写 常见 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“当每个指针单调前进时，总移动次数通常 O(n)”。
- 误区：重复值和边界值不会改变代码。 若移动后仍无法证明排除安全，就不能仅凭“连续区间”使用双指针。
- 追问：为什么每次推进不会漏掉答案？ 因为始终维护“指针移动必须一次排除一批不可能状态，并保证被丢弃状态不含答案”，被舍弃区域已由顺序或状态关系证明不可能更优。
- 追问：用一个数字例子怎么讲？ 可以从“两数之和从 n² 对枚举降为左右合计最多 n 次移动”开始，逐轮写出状态与被排除区间。
- 追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“哈希、前缀和、二分和单调队列解决不同结构”。
- 追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。
九、加强记忆
双指针用两指针配合遍历,把 O(n²) 降到 O(n),分三类:对撞指针(左右相向,利用有序性夹逼——两数之和、反转、三数之和、盛水);快慢指针(同向不同速——原地修改数组读写分离、链表判环/中点);滑动窗口(同向维护区间,右扩左缩——连续子串/子数组求最长/最短)。识别:有序两端夹用对撞、原地筛选用快慢、连续区间用滑窗。正确性关键是「移动一步排除一批、不重不漏」。