作为一个常年跟算法题打交道的开发者我打算开一个「优选算法专题」系列专门挑那些面试里出现频率最高、实际工程里也真能派上用场的算法模型逐个拆开揉碎了讲。第一期就选双指针——这玩意儿在LeetCode和各大厂笔试题里属于“必须拿分”的送分题但很多新手第一眼根本看不出它跟暴力的区别更不知道怎么判断一道题该用双指针。这篇文章不是简单罗列几道题的题解而是要把双指针的底层逻辑讲透它凭什么能把O(n²)的暴力优化到O(n)什么时候用对撞指针什么时候用快慢指针什么时候又该上滑动窗口每类怎么识别题目特征、怎么写边界条件、怎么调试跑偏的指针我会结合具体代码和踩过的坑来讲看到最后你至少能自己判断新题该往哪个方向套。这篇干货适合准备校招社招的开发者、搞竞赛的选手以及工作中需要自己写高效遍历逻辑的同学。1. 双指针到底在解决什么问题先别急着看题想明白一个问题双指针为什么能优化暴力解法因为暴力解法里大量时间浪费在“重复扫描”和“无效比较”上。比如两数之和的暴力写法两层for循环固定一个数再把剩下所有数都扫一遍去找目标差值大量比较其实是白做的。双指针的思路是让两个指针按某种规则有节奏地移动每次移动都跳过那些已经被证明不需要再看的元素把遍历范围从“全量扫描”压缩成“有方向的扫描”。1.1 从暴力到双指针的核心优化逻辑用一个很生活的例子帮助理解假如你面前有一排从矮到高排好的队伍你想找到两个人身高之和恰好等于某个值。暴力做法是让第一个人站在原地让第二个人从队头到队尾挨个试试完换第一个人站的位置再让第二个人从头再试一遍。这里最大的浪费在于第一个人已经变矮了第二个人其实不需要从队头重新开始因为队伍整体有序一高一矮两个指针从两端往中间逼近反而能快速锁定答案。这个例子对应的就是有序数组上的对撞指针数学上它依赖一个关键性质单调性。当数组有序时左指针向右移动会让和变大右指针向左移动会让和变小于是我们可以根据当前和与目标的大小关系决定移动哪一侧指针从而把搜索空间从矩阵级别的两两组合压缩成一次线性扫描。注意暴力解法O(n²)本质是在遍历一个n×n的二维组合空间双指针能做的是沿着这个二维空间的对角线附近走一条折线路径每一步都能排除一整行或一整列的可能性。更广义地说双指针适用于两类场景。第一类是“需要在有序或部分有序结构中找满足条件的配对”典型题是对撞指针类的两数之和、三数之和、盛最多水的容器。第二类是“需要同时维护两个位置来刻画一段连续区间”典型的是快慢指针找链表中点、判断环以及滑动窗口类的子串问题。后者的优化逻辑也类似右指针负责扩张探索新元素左指针负责在条件不满足时收缩抛弃旧元素中间没有重复扫描窗口整体只遍历序列一遍。1.2 双指针的三种基本模型在实际做题中双指针并不是一种固定的写法而是有三大流派左右对撞指针。两个指针分别从数组的头和尾出发相向而行通常要求数组有一定顺序特征要么天然有序要么能通过排序保证单调。它适合处理“从数组中找出两个元素满足某种关系”的问题比如两数之和、判断回文串、反转数组。快慢指针。两个指针从同一位置出发步长不同一个走得快一个走得慢通常用在链表或数组里判断环路、找中间节点、找重合节点。它依靠的是“在环形轨道上速度不同的人终将相遇”这个朴素物理直觉。滑动窗口。本质上也是两个指针维护一段区间右指针不断右移扩展窗口左指针在窗口状态不合法时右移收缩窗口。它特别适合处理“连续子序列/子串”类问题比如最大无重复子串、最小覆盖子串核心是保证窗口内的状态信息可以被高效维护。判断一道题该用哪种模型有一个很实用的识别方式如果题目里出现“连续”“子串”“子数组”这类字眼优先考虑滑动窗口如果出现“有序”“两两配对”“求和比较”优先考虑对撞指针如果题目对象是链表或者需要判断是否有环、找中点优先考虑快慢指针。这个套路在绝大多数面试题里都是有效的。2. 左右指针最经典的对撞思路对撞指针是双指针模型里最好理解、也最容易被忽视细节的一类。它代码量不大但移动指针的时机和终止条件一旦写错就容易出现越界或者漏解。我们先从最经典的“有序数组两数之和”入手把整个推导过程走通。2.1 两数之和的推导与代码实现题目描述很简单给定一个升序排列的整数数组找出两个数使它们的和等于目标值返回这两个数的下标。看到这个题第一反应可能是用哈希表做一次遍历这当然行。但如果要求不开额外空间或者面试官明确不让用哈希双指针就更适合。原因是数组已经有序左指针l初始指向第一个元素右指针r指向最后一个元素计算sum nums[l] nums[r]。如果sum小于target说明当前左指针指向的数太小右指针已经不能再大了那只能把左指针向右移动一位来增大sum如果sum大于target说明当前右指针指向的数太大左指针已经不能再小了那就把右指针向左移动一位来减小sum。这样每调整一次就排除掉一个不可能的解最终在O(n)时间内找到答案。这里有一个值得深挖的关键点为什么left之后不需要重新考虑right那边已经走过的元素因为数组有序且left位置的数变大了如果之前left固定时right-1位置的数加进去都凑不够target那么left再往右数更大时right-1之后的元素更不可能凑够反方向同理。这正是单调性保证的剪枝逻辑。写代码时注意循环条件是while (left right)而不是while (left right)因为两个指针指向同一个元素时不能算两个数。来看标准实现vectorint twoSum(vectorint numbers, int target) { int left 0, right numbers.size() - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { return {left 1, right 1}; } else if (sum target) { left; } else { right--; } } return {-1, -1}; }这个代码很精简但有几个容易出错的细节。第一返回值要求下标从1开始时记得left1、right1。第二在“sum target”的分支里一定要先移动left再进入下一轮循环不要忘记写left。第三如果找不到答案循环会自然结束返回一个约定好的无效值。核心代码不算难难的是你能不能给面试官讲清楚“为什么一定能找到答案”以及“为什么复杂度是O(n)”。2.2 盛最多水的容器与回文判断另一个非常有代表性的对撞指针题目是盛最多水的容器给一个非负整数数组每个元素代表一个高度在坐标轴上画n条竖线找两条线能容纳最多的水。暴力做法是两层循环枚举所有线对复杂度O(n²)。用双指针则从最宽的位置开始left在0right在n-1面积 min(height[left], height[right]) * (right - left)。此时宽度已经是最大值了唯一的可能性在于提高高度所以策略是“哪个指针指向的板矮就移动哪个指针”因为矮的那块板决定了当前面积的上限只有换掉矮板才有可能让面积变大。这个策略背后的原因值得细想如果移动较高的板新板的高度要么更矮、要么不变而宽度一定变小面积不可能超过当前值所以这个方向可以直接放弃。移动较矮的板虽然宽度同样变小但高度有可能增大从而让面积变大。每一步都在“用宽度换高度”直到两个指针相遇记录过程中最大的面积。这样的结论在面试里经常被追问你要能说出来“每次移动矮板保证不会漏掉最优解”才算真懂。int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int area min(height[left], height[right]) * (right - left); ans max(ans, area); if (height[left] height[right]) { left; } else { right--; } } return ans; }再举一个对撞指针的常见变体判断一个字符串是不是回文也可以两个指针从头尾同时向中间靠逐对比较字符是否相等。大部分人会选这个写法因为它最直观。如果题目升级到“验证回文串只考虑字母数字字符且忽略大小写”或者“最多可以删除一个字符能否变成回文”同样能通过对撞指针加上一个“容错标记”来解决。遇到这类题先想能不能用对撞指针往往能写出非常干净的代码。3. 快慢指针链表与数组里的追击战快慢指针的核心思想是“两个人同向出发速度不同最终会在某个特殊位置相遇或拉开距离”。它最常见的应用场景是链表判断单链表是否有环、找到环的入口、找到链表的中间节点、找到倒数第k个节点。这些题目用暴力或哈希表也能写但快慢指针能让空间复杂度降到O(1)而且代码非常优雅。3.1 判环与环入口的数学推导先看最经典的141题——判断链表是否有环。定义slow和fast两个指针都从head出发slow每次走一步fast每次走两步。如果链表里没有环fast会先走到null直接返回false如果有环fast最终会在环里绕圈并追上slow两者相遇即证明有环。这里有一个小细节为什么不是三步四步而是二倍速因为步长选择二能在保证不错过相遇的情况下最简单直观步长再大就可能出现“跨过去”的情况处理起来更复杂。bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }升级版是142题不仅要判断是否有环还要返回环的入口节点。这个题的推导很有意思网上很多人直接背结论“相遇后一个指针从head重新走另一个从相遇点走再次相遇处就是入口”但很少有人解释为什么。其实可以由相遇关系推出来假设head到环入口的距离是a入口到相遇点的距离是b相遇点绕一圈再回到入口的距离是c。slow走了abfast走了abcb也就是入环后又绕了快一整圈才追上由于fast速度是slow的两倍所以fast的路程是slow的两倍abcb 2(ab)推出a c。也就是说从head到入口的距离恰好等于从相遇点继续走到入口的距离。于是让一个指针从head出发另一个从相遇点出发都一次走一步它们一定会在入口处相遇。这个推导我建议你亲手画一遍因为面试官非常喜欢追问这一题能画出这个图并且用数学关系说明“a等于c”基本就过关了。我之前在给一个学员辅导时他用暴力哈希的做法过了OJ但一被问到原理立刻卡壳后来我把这个图画了一遍他印象就深多了。算法学习里图和推导是让理解持久的关键。3.2 链表中点与数组特化用法除了判环快慢指针还有一个非常高频率的应用找链表的中间节点。用slow一次走一步fast一次走两步当fast到达链表末尾时slow恰好停在中间。这个解法的时间复杂度O(n)空间复杂度O(1)比先遍历计数再遍历一半的方式少了一次遍历实际操作中也更好写。找中点在链表排序、链表反转等操作里经常要用到比如归并排序链表时就要递归地找中点拆分链表。ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }快慢指针在数组上同样有妙用。最经典的是“原地移除重复元素”数组已经有序要求原地去重并返回新长度。此时可以用一个慢指针i指向“新数组的最后一个位置”快指针j遍历整个数组遇到不同的元素就把它放到i1的位置上最后返回i1。这个写法很像滑动窗口的雏形但更准确地说它是“读写指针”模型——慢指针指向写入位置快指针负责扫描读取。int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int i 0; for (int j 1; j nums.size(); j) { if (nums[j] ! nums[i]) { i; nums[i] nums[j]; } } return i 1; }这个题目在工程上也有对应场景比如清理有序配置列表中的重复项或者对日志里按时间排序的记录做去重。很多人容易在边界条件上翻车当数组为空时直接访问nums[0]会崩溃所以必须先判空。另外注意循环结束后返回的是i1而不是i因为i是最后一个不重复元素的下标长度需要加1。这类“读写指针”在字符串压缩、移动零、颜色分类等题目中会反复出现掌握了模型做题速度会明显提升。4. 滑动窗口双指针最灵活的变体要说双指针家族里最值钱的一个分支我首推滑动窗口。它几乎是所有“连续子数组/子串”题目的通用解从最长无重复子串到最小覆盖子串从长度最小的子数组到字符串排列全都能用。滑动窗口的核心其实就是两个指针维护一个区间配合一个“窗口状态”数据结构来记录窗口内元素的情况。4.1 最长无重复子串的窗口维护先看LeetCode 3最长无重复字符的子串。题目要求在一个字符串里找到最长的一段连续子串使得其中没有重复字符。最直接的思路是用一个哈希集合记录窗口里的字符然后交替移动左右指针。具体过程右指针不断向右扩展把新字符加入集合。如果新字符已经在集合里了说明窗口里有重复那么左指针就要向右移动并且把离开窗口的字符从集合中移除直到重复字符被赶出窗口。整个过程中窗口始终保持“没有重复字符”的合法状态每次记录窗口宽度取最大值即可。int lengthOfLongestSubstring(string s) { unordered_setchar window; int left 0, ans 0; for (int right 0; right s.size(); right) { while (window.count(s[right])) { window.erase(s[left]); left; } window.insert(s[right]); ans max(ans, right - left 1); } return ans; }这里有好几个初学者容易错的地方。第一while循环而不是if新字符可能和窗口里多个位置重复虽然这个题最多一个但严格写法用while更安全用if处理会漏删元素。第二先删除left指向的旧字符再left顺序不能反过来否则删的就是新位置的元素。第三插入新字符要放在while结束之后否则先插入会干扰判断。第四每一轮循环都要更新ans包括窗口长度为1的情况所以别忘了max比较。如果面试官继续追问“能不能优化到不用while”答案是可以用哈希表记录每个字符上一次出现的位置直接把left跳到max(left, 上次位置1)。这个优化在字符集很大时也能保持线性复杂度但基础版本已经是一个完整的解法。我建议先把基础写熟练再说优化面试场上不会因为没用优化就不给分。4.2 最小覆盖子串的条件管理比最长无重复子串再难一档的是最小覆盖子串给你一个字符串s和一个模式串t找出s中包含t所有字符的最小子串。这里不能用一个简单的集合来判断窗口是否合法了因为t里可能有重复字符比如t AABC窗口里必须有至少两个A、一个B、一个C才算覆盖。因此需要用一个哈希表记录t中每个字符的需求量再用另一个哈希表记录窗口中每个字符的数量然后维护一个计数器表示“已经满足数量要求的字符种类数”。当计数器等于t中不同字符的种类数时窗口合法就可以尝试移动左指针收缩窗口寻找更短解。string minWindow(string s, string t) { unordered_mapchar, int need, window; for (char c : t) need[c]; int left 0, right 0; int valid 0; int start 0, len INT_MAX; while (right s.size()) { char c s[right]; right; if (need.count(c)) { window[c]; if (window[c] need[c]) valid; } while (valid need.size()) { if (right - left len) { start left; len right - left; } char d s[left]; left; if (need.count(d)) { if (window[d] need[d]) valid--; window[d]--; } } } return len INT_MAX ? : s.substr(start, len); }这段代码是滑动窗口的“标准模板”理解之后几乎能套用在所有子串问题上。注意几个位置的细节右指针右移扩展窗口时先更新窗口数据再判断合法性左指针收缩时先判断这个字符是否会影响“合法状态”再更新窗口数据valid只在“窗口中该字符数量恰好等于需求量”时加一离开该状态时减一这样可以避免反复比较整个哈希表。如果字符种类多、比较频繁这个计数器的存在能让时间复杂度维持在O(n)。实际上还有一类问题叫“固定窗口大小的滑动窗口”比如找到大小为k的子数组最大平均值、字符串排列等等把window当成一个固定长度的窗口右指针移动后左指针立即跟随移动本质上是上面模板的特例。4.3 滑动窗口模板的适用边界学滑动窗口的时候最怕的是不知道什么时候不能用。这里的判断标准并不复杂要求求解的目标必须是“连续子数组/子串”相关的属性而且窗口的状态必须可以高效维护。如果题目描述里没有“连续”这个概念比如要求从数组里挑任意几个数凑出目标值那滑动窗口就不适用优先考虑动态规划或回溯。还有一种情况要特别小心数组里有负数时窗口的“从小到大”单调性可能会被破坏。比如“和大于等于target的最短子数组”这个经典题正数数组可以用窗口不断右移因为加上正数会变大减去正数会变小可以放心收缩但如果数组带负数加一个负数和减一个负数会让窗口和的行为变得不规则双指针的收缩策略就失效了。遇到这种情况要么换算法要么把数据预处理成满足单调性的形式。我在实际练习中见过不少人把带负数的题硬套滑动窗口最后得到错误答案排查半天才发现是数据性质不满足前提。另外一个适用性边界与“窗口内状态的合并与撤销”有关。如果每次移动指针时更新窗口状态的代价不是O(1)而是需要扫描整个窗口那总复杂度可能就会退化成O(n²)这时候滑动窗口的优势就没了。比如某些需要维护窗口内次大值的题目只靠普通哈希表是不够的要配合单调队列或堆来维护。所以做题时除了想到用滑动窗口心里还要过一遍“状态维护成本”这件事。5. 双指针的常见陷阱与调试心得说实话双指针题目代码都不长真正拉开差距的是细节。我在刷题和带人过程中总结了一批高频踩坑点这里一次性列出来每一条都是真金白银换来的经验。建议你把这些内容收藏起来做题前快速过一遍。5.1 边界条件与终止时机最常见的问题出现在循环终止条件上。对撞指针一般用left right等于的情况看题意快慢指针在链表中一定要先判断fast和fast-next非空否则访问空指针直接崩溃。滑动窗口里右指针到达末尾后有些题目还需要再收缩一轮左指针来更新答案不要着急退出。举个具体的例子在“长度最小的子数组”这题中常见的错误写法是在right到达数组末尾后直接结束循环但此时左指针可能还有收缩空间能找到一个更短的合法窗口。正确的做法是外层while结束后单独再跑一次内层收缩循环或者把收缩逻辑写在每次右移后的while里并在right到末尾后额外处理一次。很多博客没有点出这个细节导致新手照抄模板后总差一两个用例不过。另一个边界问题是下标为0的起始状态。比如对撞指针初始化left 0、right n - 1是没问题的但有些题目要求找“两个数的下标差值至少为k”那么right的起点就不是n-1而是要改成right left k。这类题目本质还没变但初始化变了整个推导都要跟着重来所以审题非常重要。5.2 指针移动顺序与状态撤销在滑动窗口里指针移动顺序是一个极容易出错的重灾区。右指针扩展时先移动right再根据新元素更新窗口状态左指针收缩时先根据当前left指向的元素更新窗口状态通常是减少计数的操作再把left向右移动。一句话记忆先更新状态再移动指针。很多人写着写着就变成先移动指针再更新状态结果统计到的永远是下一个位置的情况导致答案偏差。快慢指针里也有类似问题。比如找链表中点while条件是fast fast-next循环体内先移动slow再移动fast这个顺序其实是固定的但如果题目要求找“环入口前的节点”或“倒数第k个节点”指针移动的先后顺序也要跟着调整。遇到这类变体建议先在纸上画链表走两三个节点模拟一下别急着写码。状态撤销的另一个常见问题是窗口数据的“回滚”。在最小覆盖子串中左指针收缩时如果当前字符在need里要先判断它是否让valid减一再把window里的数量减一顺序不能反。如果先减window[d]再判断window[d]已经变了判断条件就不准了。这种微妙的顺序问题编译器不会报错也不会立刻让答案变得离谱可能只是某些输入下差一个字符排查起来非常头大。我的习惯是每次写这类代码都强制自己“把状态更新语句和指针移动语句分别列成两行”用注释标注清楚这样即使错了也容易定位。5.3 双指针的剪枝优化套路基础的双指针可以过很多题但遇到一些数据量大的场景还需要做一些剪枝优化。第一个套路是去重。在三数之和这类题里排序之后用对撞指针找两数之和如果当前数和上一个数相同就可以跳过避免产生重复三元组。注意跳过逻辑要写在指针移动循环里同时判断left right不然越界。第二个套路是提前终止。排序后如果最小的数加起来已经大于target可以直接退出外层循环不用再往后看了对于已排序数组如果当前left指向的数和最右侧的数相加还小于target说明left一定不够直接left甚至可以用二分法加速定位下一个left的位置。这些优化单独看都不难但组合在一起会让算法的执行效率明显提升也更容易在竞赛或者卡常的题目里通过。我参加竞赛时有个习惯先用最直白的双指针写出一版能过小数据的代码再根据题意做剪枝优化最后再针对最坏情况调参。直接从优化版本开始写容易把逻辑绕晕还不一定对。6. 按题型刷题路线与学习建议最后给一条比较实用的刷题路线按照难度递进安排适合刚从“暴力解”过渡到“双指针”的选手。这条路我自己走过也推荐给很多学弟学妹反馈都还不错。第一步先把基础模型打牢。做LeetCode 1两数之和、167有序数组的两数之和、344反转字符串三题感受对撞指针的写法。这三题简单但很能训练“指针移动条件”的肌肉记忆。第二步进入快慢指针专题。做141判环、142环入口、876链表中点、19删除倒数第N个节点重点是体会慢指针如何“滞后”于快指针以及边界条件怎么处理。第三步专攻滑动窗口。做3无重复最长子串、76最小覆盖子串、567字符串排列、438找到字符串中所有字母异位词这四题几乎覆盖了滑动窗口的全部套路。第四步挑战综合题。做15三数之和、11盛水容器、42接雨水这三题要求在对撞指针的基础上进行剪枝和状态比较是面试中的高频困难题。刷题的时候有几个小提醒。一是别只刷一遍双指针这类题间隔两周再刷一遍效果远好于连续刷十题。二是写代码的时候把前面说的“先状态更新再移动指针”当作默认习惯刻进DNA能省去大量调试时间。三是每题做完后试着不看代码把这个题的移动逻辑用一两句话说清楚说清楚了才是真懂说不清楚大概就是背题下次换个包装就歇菜了。我自己的体会是双指针最迷人的地方在于它把“搜索”变成了一种“逼近”。暴力是做决策我在n个选项里挨个试双指针是推理这一步走完我确定哪些区域不可能有答案直接删掉。这种思维方式在工程里也很有用比如在有序数据里做范围查询、在日志时间戳里定位事件窗口、在压缩算法里维护滑动字典底层都是同一套逻辑。多花点时间把双指针吃透它绝对会成为你算法工具箱里最趁手的一把刀。