双指针算法这块内容我拖了很久才决定把它彻底梳理一遍。原因挺简单很多题看题解觉得就两行代码可真到自己写的时候要么左右边界搞错要么死循环要么边界条件漏掉。后来我把双指针相关的题目集中刷了一遍才真正摸清楚它的脾气。这篇算是双指针的完整总结从原理到代码、从基础模型到变体应用一次讲完。适合已经会写数组遍历、链表基本操作但是对双指针场景还比较混乱的读者也适合准备面试前快速回顾的人。1. 双指针算法的本质为什么两个指针就够了1.1 从暴力解到双指针复杂度的跃迁我们见到的绝大多数双指针题目暴力解法都是两层循环。以“有序数组中找到两个数使它们的和等于目标值”为例直接枚举 i、j 组合时间复杂度 O(n^2)。双指针版只用一个左指针、一个右指针从数组两端往中间走每轮只移动一个指针最多移动 n 次时间复杂度降到 O(n)。这个复杂度跃迁不是靠什么魔法靠的是剪掉大量“不可能成为答案”的枚举区间。关键在于理解如果数组有序假设当前 nums[left] nums[right] target那不仅当前 right 不可能是答案所有比当前 right 更小的 right 位置都不可能满足条件。我自己的理解方式是固定 left如果当前右侧最大值加上 nums[left] 都还小于 target那右侧更小的值更不可能满足条件所以只能让 left 往右移动换一个更大的左侧数。同理如果和大于 target说明 nums[right] 再往左侧之和更小才能满足右侧已经固定所以 right 必须向左移。每移动一步就少了一批状态循环很快就结束。这个剪枝成立的前提是单调性数组有序时指针向右移动数值只增不减向左移动数值只减不增。没有单调性双指针大概率失效硬套反而会把正确答案筛掉。1.2 指针移动的单调性双指针能用的前提为了保证单调性数组题通常要先排序。但有两点容易被忽略第一排序会改变元素原本的相对顺序如果题目要求返回原始下标那排序后就得在结构体里存原 index或者改用哈希表第二并不是所有双指针都依赖有序数组比如链表判环、求中点、快慢指针它们利用的是“移动步长差”和链表的拓扑结构跟数值大小无关所以不需要排序。我在实际刷题中总结了一条判断规则如果题目中出现了“数组、连续子段、两个元素、不重复对”这些关键词并且能通过移动两端来排除不可能区间就可以往双指针上想如果题目要求所有组合通常要先排序再配合去重逻辑。这里的“单调性”是动态变化的比如滑动窗口里的单调性是“窗口扩大满足条件窗口缩小破坏条件”本质上也是一种单调关系。所以双指针并不是一个具体代码模板而是一种“利用约束条件单向移动来压缩搜索空间”的思想。2. 两大经典模型对撞指针与快慢指针2.1 左右对撞从两端向中间逼近对撞指针是最直观的双指针left 从数组头部开始right 从尾部开始每轮根据条件让 left 或 right--直到两个指针相遇。经典场景是有序数组两数之和、反转字符串、判断回文串。拿“盛最多水的容器”举例子给定一个数组 heightheight[i] 代表位置 i 的挡板高度要找到两条线能盛的水最多。暴力是所有组合O(n^2)。双指针 left0rightn-1当前容积是 (right-left) * min(height[left], height[right])。如果 height[left] 更矮那么不管 right 怎么往左移只要 left 不动容器高度不可能超过 height[left]而宽度减小所以左边界固定时最优已经就是当前状态于是只能 left尝试换一个更高的左板反之 right--。这个过程是很多人会产生疑问的地方为什么不移动高的那边因为移动高的那边容积上限只会被矮的那边卡死还白白缩短了宽度不可能得到更优解。这个“移动受限侧的指针”原则在对撞类题目里反复出现。判断回文串更简单左右指针分别指向首尾字符相等就 left、right--一旦出现不等就不是回文。这里面需要注意跳过空格、标点和大小写的情况本质上是“过滤后继续比较”我一般先把字符串预处理成只保留字母数字的小写形式虽然多花 O(n) 空间但逻辑清楚面试时不容易写乱。2.2 快慢指针数组与链表里的“同步赛跑”快慢指针本质上是两个移动速度不同的指针遍历同一个结构。最著名的应用是链表判环slow 每次走一步fast 每次走两步。如果链表中不存在环fast 会先到达 null如果存在环fast 和 slow 一定会在环内相遇。为什么步长选 2 而不是 3步长差为 1保证在环内追赶时fast 每轮与 slow 的距离严格减少 1绝对不会跳过相遇点。如果步长差大于 1可能出现 slow 在某个点、fast 正好跨过它的位置导致虽然都在环里但多次错过实现起来也增加了边界判断。判定环之后如果还需要找环入口经典步骤是相遇时把一个指针移到 head另一个留在相遇点两者都每次走一步再次相遇的点就是环入口。这个结论背后有数学推导假设 head 到入口距离是 a入口到相遇点距离是 b环剩余长度是 c那么 slow 走了 abfast 走了 abk(bc)k 是绕的圈数由于 fast 速度是 slow 两倍得到 2(ab)abk(bc)即 a(k-1)(bc)c。当 k1 时 ac也就是说让一个指针从头走 a 步另一个从相遇点走同样步数正好在入口汇合。看到推导别害怕实际记住结论就能用。快慢指针还能用来求链表中间节点fast 走两步、slow 走一步fast 到末尾时 slow 恰好在中点。这里要注意链表长度的奇偶性我习惯让 while(fast ! null fast.next ! null) 作为循环条件循环结束后 slow 指向的位置就是中点如果希望偶数长度时取靠左还是靠右的那个初始化方式需要微调。这种细节在涉及树平衡、回文链表中点比较时很容易成为隐藏扣分点。3. 滑动窗口双指针真正的杀手级应用3.1 窗口与指针的关系滑动窗口算是双指针里最容易写崩、也最常考的一类。它的模型是用 left 和 right 维护一个 [left, right] 的连续区间right 不断右移扩大窗口当窗口内的状态不满足题目约束时left 右移缩小窗口直到重新满足。每次窗口满足条件时就能更新一次答案。这个模型解决的核心问题是“找满足某种约束的最短/最长连续子数组/子串”。比如“无重复字符的最长子串”或者“和大于等于 target 的最短子数组”。它跟普通双指针的区别在于左右指针不是从两端向中间移动而是都从起点出发像一把可以伸缩的尺子沿着序列滑动。由于每个元素进窗口一次、出窗口一次整体复杂度 O(n)。写滑动窗口的关键是先明确四件事第一窗口是什么左右指针包围的连续子序列第二窗口状态用什么维护计数数组、哈希表还是累加和第三什么时候缩小窗口不满足约束时第四什么时候更新答案收缩前还是收缩后还是每个位置都更新。我见过不少人在第三、第四点上踩坑其实只要记住扩大窗口是“试探”缩小窗口是“恢复合法”答案一定在窗口合法时产生。3.2 模板与实现细节下面这个模板是我自己整理后感觉最好用的一套基于哈希表和计数器适用于大部分字符串/数组子段问题用 Python 写def sliding_window(s, condition): n len(s) left 0 counter {} # 维护窗口内元素的出现次数 ans 0 # 根据题目要求改成最短长度、最大长度、具体子串等 for right in range(n): # 1. 右指针进入窗口更新状态 counter[s[right]] counter.get(s[right], 0) 1 # 2. 如果窗口不满足约束左指针右移缩小窗口 while not condition(counter): counter[s[left]] - 1 if counter[s[left]] 0: del counter[s[left]] left 1 # 3. 此时窗口合法更新答案 ans max(ans, right - left 1) return ans注意几点一是 while 而不是 if因为左指针可能需要连续移动好多次才能恢复合法二是窗口内计数的删除和自减不能省否则后续判断会出错三是答案更新位置可以放在循环结束时也可以放在 while 内部每次收缩后取决于题目问的是最长还是最短。求最短子串时答案更新通常要放在 while 收缩过程中因为只有左边界往右收缩时才能产生更短的合法窗口。以“无重复字符的最长子串”为例condition 具体化为counter 中所有字符计数都不超过 1。上一轮右指针加入后如果计数大于 1进入 while 循环不断把 s[left] 移出窗口并 left直到重复字符的计数回到 1。由于 while 内每移出一个字符就少一个状态最坏情况下每个字符被 left 和 right 各访问一次所以还是 O(n)。这道题也可以用数组记录每个字符最后出现的位置来优化但计数哈希表的模板通用性更强我建议先掌握通用版再针对具体题做空间优化。再补充一个滑动窗口容易出错的地方如果窗口内维护的是“种类数”而不是“出现次数”比如“最长子串恰好包含 K 种字符”那 condition 判断的是 len(counter) K收缩时同样要注意删除计数为零的 key。我用计数器加一个变量 types 来记录当前有多少种字符可以避免频繁调用 len(counter)在长字符串上效率高不少。4. 双指针的常见变体与其它算法的配合4.1 三指针、多指针与分区问题双指针再往前一步就是三指针甚至多指针但核心还是“约束条件下的定向移动”。最有代表性的三指针是荷兰国旗问题也就是对只包含 0、1、2 三种值的数组进行原地排序。用 red 指向 0 区域的下一个位置blue 指向 2 区域的前一个位置current 从头扫描到尾遇到 0 就与 red 交换、red、current遇到 2 就与 blue 交换、blue--但 current 不前进因为换过来的值还没判断遇到 1 直接 current。这里很多人会漏了“遇到 2 交换后 current 不前进”这一步如果不理解交换过来的值需要重新判断排序结果就会乱。再看三数之和数组里找所有和为 0 的三元组要求不重复。常规流程是排序然后枚举第一个数剩下两个数用对撞指针在右侧区间找组合同时跳过重复元素。枚举第一个数时如果 nums[i] 已经大于 0 就可以直接 break因为数组有序后面三个正数之和不可能为 0。对撞指针内部当找到一组满足条件的组合后left 和 right-- 要把所有重复值都跳过否则会出现重复三元组。这个“去重”和“剪枝”是面试官非常喜欢追问的细节代码实现时必须注意是在找到答案之后去重而不是在移动指针前盲目去重。4.2 双指针与二分、排序、贪心的关系双指针往往会和别的算法一起出现。我自己的体会是二分查找本质上也是一种“指针收缩”只不过它每次只移动一个区间端点而且移动的幅度是折半不是一步一步走。在有序数组里做搜索二分是更激进的单指针收缩当搜索空间是两个维度比如两个有序数组的 TopK 问题双指针又可以作为二分的辅助。双指针不是孤立的技巧更像一种“在可行解空间里沿单调方向剪枝”的世界观。排序算法里也处处是双指针快速排序的 partition 用两个指针从两端往中间扫描并交换元素归并排序的 merge 用两个指针分别遍历左右子数组每次取更小的那个放入结果。所以说双指针是数据结构和算法的基础设施不是某个专题的偏门技巧。你甚至可以把很多贪心策略理解为双指针的决策规则每次移动哪个指针本质上就是一次贪心选择。比如“盛最多水的容器”里移动短线这就是在局部最优中选择不会错过全局最优的那个方向。要用好双指针我建议先做到“识别单调性”再问自己我移动哪个指针不会漏解只要这个问题的答案清晰代码怎么写都差不到哪去。5. 实操中容易踩的坑与排查技巧5.1 边界条件与初始化我在代码评审中看过最多的双指针 bug几乎都出在边界条件上。第一是 while 条件对撞指针通常用 left right滑动窗口通常用 right n而“允许空区间”时可能要用 left right。如果你判断回文串时用 left right中心字符会被判断一次结果一般不影响但如果循环里有 a[left] 和 a[right] 的交换操作left right 时交换没有任何意义却不会报错。最怕的是该用 left right 却用了 同时 right 初始为 n导致第一轮就访问 a[n] 越界。第二是 right 初始值是 n-1 还是 n一定要根据题目语义定。对撞指针从两端向中间靠拢right 一般是 n-1滑动窗口右指针代表下一个待加入的元素通常从 0 开始。还有一些题会用“虚拟尾指针”的写法比如判断链表中点fast 条件写成 fast ! null fast.next ! null能避免空指针。整这些细节没什么捷径唯一的办法是每个模板都要自己从头推导一遍而不是背。5.2 典型错误案例我列出几个高频错误指针更新顺序错。有人在移动 left 前就用了 left 1 位置的元素导致漏掉当前元素。比如处理连续子数组时应该先更新计数再 left如果写成先 left 再更新计数就会把窗口外的元素算进来。死循环。滑动窗口的 while 里如果 left 没有前进或者前进后没有同步修改窗口状态进入死循环是必然的。调试时我看到有人为了退出循环而加 break这是掩耳盗铃根本问题还是状态和窗口边界没同步。重复计算。有些双指针解法更新答案时把已经统计过的子数组又算了一遍结果要么重复要么导致答案偏大。比如统计“以 right 为结尾的合法子数组个数”时每次增加 right - left 1这是一个非常常见的计数技巧但很多人不知道怎么来的。排查这类问题我最常用的方法是在 while 循环开头打印 left、right 和当前窗口状态。数据规模大的时候不用全打挑一个长度为 5 左右的小数组手动模拟一遍。如果手动模拟和代码输出不一致说明你对“移动哪个指针”的理解还有偏差。把错误案例记录下来比刷十道新题更有用。5.3 实测经验到底怎么练双指针说点实际的。我练双指针的阶段分三步走。第一步先刷 10 道基础题包括有序数组两数之和、判断回文串、链表判环、链表中点、无重复字符最长子串、长度最小的子数组把这些题反复写直到不看题解也能默写出模板。第二步把每道题改成“返回所有答案”或者“返回区间端点”这种变体强迫自己改代码比如两数之和改成三数之和再改成四数之和能明显感受到指针去重的难点。第三步做混合题比如“双指针 二分”“双指针 哈希表”的题目训练自己判断用哪种辅助结构的敏感性。刷题这件事我不建议只追求数量。每道双指针题做完后我都会在代码注释里写一句“为什么这一步必须移动 left 而不是 right”下次回看时能快速唤起思路。这也算是我个人整理系列遗留内容时的一个习惯把原理写清楚比刷十道新题更有用。双指针这块写完之后我对很多数组和链表题的判断都比以前自信希望你也能体会到这种“突然看穿”的感觉。最后再分享一个小技巧当你在一道题里看到“连续子数组”“区间”“两个元素和”这类词先不要急着上复杂数据结构试着在草稿纸上画两个指针分别标出“移动哪个指针会让答案变大/变小”如果能找出一个单向的排除规则双指针基本上就是解。这个办法我屡试不爽尤其是面试时间紧张的时候它往往能帮你快速定位到正确方向。