到O(n)的优化实战)
刷算法题这段时间双指针应该是我用得最频繁的一类解法。它不算某个具体算法更像是一套代码组织思路——在数组、链表、字符串这类线性结构上同时维护两个指针来遍历、比较或计算。许多一眼看去要两层循环暴力枚举的问题换成双指针后一遍扫描就能搞定时间复杂度从O(n^2)直接降到O(n)。这篇文章我把双指针的常见模型拆开讲一遍再配合几道经典算法题把边界条件和指针移动时机都说明白。适合刚开始刷题的新手也适合面试前突击双指针专项的朋友。很多人把双指针当成一堆零散技巧在背其实它背后是利用单调性减少无效枚举这一条核心逻辑。对撞指针、快慢指针、滑动窗口、分离双指针本质上只是四种不同的指针配合方式。把这层底层逻辑想明白再去看任何双指针题思路都会清晰很多。下面先从什么时候该用双指针讲起。1. 双指针能解决什么问题从适用场景到底层逻辑1.1 什么时候该往双指针上想先说我自己的判断标准。题目里如果出现有序数组连续子数组链表有环两数之和无重复子串这类关键词基本就能往双指针上靠。另一个信号是直接暴力枚举大概率超时但数据本身是线性结构、顺序关系很明显这种题用双指针往往一拍即合。我的实际操作节奏是拿到题目先花五秒钟问自己三个问题。第一数据本身是否有序或者能不能排序第二问题是否要求找一对元素、一段连续区间、链表中某个特殊位置第三暴力解的复杂度大概是多少有没有明显可以剪枝的空间如果前两个问题里有任何一个答案是第三个问题又明显超时那双指针就是我的第一优先级方案。举个例子无序数组找两数之和第一反应不直接是双指针而是先排序。排序本身O(n log n)排序之后再双指针O(n)整体可以接受。再比如判断链表里有没有环快慢双指针几乎是标准解没什么可犹豫的。双指针不挑语言、不挑平台它属于数据结构与算法基础的一部分值得好好掌握。1.2 O(n^2)到O(n)双指针到底省在哪儿这个问题我想掰开讲。以对撞指针为例数组有n个元素暴力解法枚举所有(i, j)组合需要n(n-1)/2次比较。但用左指针l和右指针r分别从两端出发每次根据当前sum与target的大小关系要么移动l要么移动r。整个过程中每个元素最多被访问两次——一次作为左指针指向它一次作为右指针指向它所以总复杂度是O(n)。快慢指针的原理也类似。普通单指针在某些场景下需要反复回头扫描快慢指针利用速度差在线性结构上交错前进整体遍历一遍就解决问题。滑动窗口则是维护窗口的左右边界右指针负责扩展左指针负责收缩整个序列也只被扫描一次。用一句不严谨但好记的话来概括双指针把盲目枚举变成了有方向的探索而这个方向来自数据结构本身的单调性。顺着这个思路理解题目比死记硬背几种子类型有用得多。2. 四种经典双指针模型一次讲透2.1 左右对撞指针有序数组的两端逼近左右对撞指针是所有模型里最好理解的。左指针从数组头部开始右指针从尾部开始根据当前计算结果的大小关系决定移动哪一侧。最经典的就是有序数组的两数之和当sum(a[l] a[r])大于target时说明右侧值太大了右指针向左移小于target时说明左侧值太小了左指针向右移。这个模型有个隐含前提——数据要有序。没有有序性移动指针就缺乏依据对撞就变成乱撞。有人会问如果数组本身无序怎么办答案很简单先排序再双指针。排序成本O(n log n)往往可以接受换来的线性扫描收益更大。见到有序数组四个字就想到对撞指针这个映射关系建议直接刻进脑子里。2.2 快慢指针链表题的主心骨快慢指针最经典的应用是链表判环。慢指针每次走一步快指针每次走两步如果有环两者一定在环内相遇。这个结论不用死记物理意义很直白快慢速度差是1在环里相当于快指针每一步靠近慢指针一步环的长度有限必然在某一步追上。除了判环快慢指针还能做不少事。找链表中间节点时快指针走两步、慢指针走一步快指针到终点时慢指针恰好到中间。删除链表倒数第n个节点时先让快指针走n步再让快慢指针同步前进快指针抵达到尾部时慢指针正好停在待删除节点的前一个位置。这几个场景基本覆盖了链表题里的高频考点练熟之后手感会好很多。2.3 滑动窗口连续子串问题的标准解法滑动窗口几乎是为连续子数组和子串问题量身定做的。右指针负责扩展窗口、覆盖新元素左指针只在不满足条件时收缩窗口。窗口内部的状态用一个set、dict或者普通变量维护窗口每一次调整后都尝试更新最优解。这个模型最关键的编写顺序是右指针移动判断当前窗口是否满足条件不满足就移动左指针收缩等到条件满足后再尝试更新答案。很多新手把更新答案放在了收缩之前导致结果永远差一点。再强调一次窗口必须是原序列中的连续片段所以删除元素永远从左侧删除不能直接抽掉中间某个值。这个细节在字符类题目里尤其致命。2.4 分离双指针两个有序序列的合并利器分离双指针常见于归并排序、合并两个有序数组、找两个有序数组的交集这类场景。两个指针各自指向不同序列比较当前指向元素的大小根据比较结果决定推进哪个指针。其实质和归并排序的核心过程一模一样。它和对撞指针最大的区别是数据源不同对撞指针处理同一个数组的两端分离双指针处理两个独立序列。实现起来不难但有个边界容易漏——其中一个序列走完后剩余元素要全部复制到结果里。这个操作漏掉的后果是合并结果少了一段而且有时候还不会立刻报错要等到用例验证才知道出了问题。模型典型场景指针方向核心前提左右对撞有序数组两数之和、三数之和相对而行数据有序快慢指针链表判环、找中间节点同向不同速链表等可循环结构滑动窗口无重复子串、最小覆盖子串同向前进连续区间问题分离双指针合并有序数组、归并排序各自推进两个序列有序3. 五道经典双指针题目实战拆解从入门到进阶3.1 两数之和 II对撞指针最典型的入门题这道题要求在有序数组中找到两个数使它们的和等于target返回下标。暴力解法是两层循环O(n^2)对撞指针写法如下def two_sum(numbers, target): l, r 0, len(numbers) - 1 while l r: s numbers[l] numbers[r] if s target: return [l 1, r 1] elif s target: l 1 else: r - 1 return [-1, -1]这个解法里最需要理解的是为什么只移动一个指针不会漏解。当sum小于target时说明当前的a[l]加上最右侧的a[r]都达不到目标那a[l]加上右侧任何一个更小的元素也必然达不到目标所以左指针可以放心右移。这就是有序性提供的剪枝依据。还有个常见误区有人觉得和太小是不是左右都要往中间动一动。答案是绝对不能同时移动两个指针。同时移动相当于跳过了l1与r的组合而这个组合可能恰好就是正确答案。对撞指针每一步只移动一侧本质上是在一个二维搜索空间中沿着一条有效的路径前进方向由大小比较决定。3.2 三数之和排序加去重的综合演练三数之和要求找出数组中所有三个数和为0的组合且不能重复。直接三重循环肯定超时标准做法是排序加双指针。先固定第一个数再在其右侧的子数组上做对撞双指针找两数之和。这里有三处细节最容易出问题第一固定的第一个数如果和上一个相同需要跳过否则会产生重复答案。第二对撞时找到一组解后l和r都要移动并且要把相邻的重复元素全部跳过才能保证下一个组合不重复。第三如果第一个数已经大于0后面的数都比它大三数和不可能为0可以直接结束循环。def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue if nums[i] 0: break l, r i 1, n - 1 while l r: s nums[i] nums[l] nums[r] if s 0: res.append([nums[i], nums[l], nums[r]]) while l r and nums[l] nums[l 1]: l 1 while l r and nums[r] nums[r - 1]: r - 1 l 1 r - 1 elif s 0: l 1 else: r - 1 return res这段代码里最妙的细节是去重的时机。找到一组解后先把左右指针移动到重复元素的最后一个位置再各走一步这样既能避开重复解又能配合外层while条件保证不越界。第二个需要留意的点是nums[i] nums[i-1]这一判断它保证固定位的首个值不重复枚举。这些细节单独看都不难组合在一起就变成了这道题最磨人的地方。3.3 最长无重复子串滑动窗口的教科书这道题要求找字符串中最长的不含重复字符的子串。暴力解法枚举所有子串并判断是否重复复杂度能到O(n^3)。滑动窗口可以做到一次遍历O(n)def length_of_longest_substring(s): seen set() l 0 ans 0 for r, ch in enumerate(s): while ch in seen: seen.remove(s[l]) l 1 seen.add(ch) ans max(ans, r - l 1) return ans这里有一个非常容易踩的坑while循环里移除的是s[l]不是ch本身。因为重复字符可能出现在窗口中间只有从左边逐步收缩才能保证窗口始终是原字符串的连续片段。如果直接remove掉ch窗口就不是一个连续区间了后面算出的长度毫无意义。我第一次写这题就在这个坑里卡了半天输出结果总是跟正确答案差一截。后来想明白滑动窗口的窗口必须语义正确删除只能从左边界进行。如果遇到窗口内大量重复的场景set的删除效率不够直观可以换成dict存储每个字符最近出现的下标左指针直接跳到max(l, dict[ch] 1)代码写起来更干净也更好解释。3.4 盛最多水的容器理解短边决定上限这道题给一组柱状高度要求选择两根柱子形成容器求最多能盛多少水。容器面积 两柱之间的宽度 x 较矮柱子的高度。暴力解法枚举所有柱对O(n^2)双指针解法是对撞def max_area(height): l, r 0, len(height) - 1 ans 0 while l r: area min(height[l], height[r]) * (r - l) ans max(ans, area) if height[l] height[r]: l 1 else: r - 1 return ans很多人理解不了为什么移动较矮的一侧就是安全的。我提供一个直观思路当前较矮柱子是height[l]那么无论右侧怎么向左移动容器高度都不可能超过height[l]因为瓶颈在左柱。此时以左柱为边界的最大可能面积是height[l]乘以当前宽度而这个上限会随着宽度缩小而递减。也就是说以这根矮柱为左边的所有情况都已经枚举到头了放弃它不会错过更大面积。反过来如果移动较高的那根柱子高度上限被矮柱锁死宽度还在减少面积只可能更小。那句移动短边本质上是因为短边决定了容器面积的天花板移动短边才有机会遇到更高的柱子来抬升天花板。3.5 接雨水双指针与动态规划的切换接雨水是双指针题目里比较难的一道。给定柱状高度求能接住的总雨水量。双指针解法的核心是当前柱子能接多少水取决于左右两侧最高柱子中较矮的那个。如果左侧最高值小于右侧最高值那当前柱子的存水量就是左最高值减去当前柱高因为右侧必然有足够高的柱子挡住雨水。def trap(height): l, r 0, len(height) - 1 left_max right_max 0 ans 0 while l r: left_max max(left_max, height[l]) right_max max(right_max, height[r]) if left_max right_max: ans left_max - height[l] l 1 else: ans right_max - height[r] r - 1 return ans这段代码维护left_max和right_max两个变量用来记录两侧遍历过程中见过的最高值。每一轮都选较矮的一侧计算雨水量再移动对应指针。我个人认为双指针版比动态规划版代码短很多但思维台阶更高。如果你刚开始刷这题建议先写动态规划版理解每列能存水取决于左右最大值中较小者这个逻辑再切换到双指针版衔接会顺很多。4. 双指针题常见的坑与排查心得4.1 指针越界所有双指针题的第一灾难双指针最容易翻车的就是数组越界。我自己总结了几条规律只要循环条件是while l r循环体里对nums[l]或nums[r]的访问就是安全的因为条件本身保证了l和r合法。但如果写成while l r循环内最后一次操作后l可能越过数组尾部后续再访问就可能崩。另一种越界出现在窗口收缩时。以最长无重复子串为例如果while ch in seen内部的逻辑写错左指针l可能一路加到超出数组范围。解决办法是收缩循环内部始终保留l r这种语义约束并且要确认每次删除的字符确实属于当前窗口。简单说双指针的每个while循环都要自己问一句这个循环靠什么停下来停下来时指针指向哪里这两个问题回答清楚越界问题基本能杜绝。4.2 指针移动时机到底先移动还是先判断这个坑在滑动窗口里尤其突出。我的习惯是先看当前状态是否需要调整再决定更新答案的顺序。两数之和里是先计算当前和再决定移动哪边最长无重复子串里是先把不满足窗口条件的字符清出去再把新字符加进来最后更新答案。这个顺序没法靠背必须理解每一步修改对状态的影响。有一个通用检查技巧把所有指针和状态变量在头脑里模拟一遍。比如右指针每走一步左指针可能连续走好几步窗口内部数据如何变化更新答案的位置是否覆盖了最优情况。动手写代码之前在注释里标出这三个动作的顺序基本不会错。4.3 死循环while条件写岔了双指针题的死循环多半是内层循环的终止条件没写对。比如三数之和里的去重循环如果写成while nums[l] nums[l 1]: l 1一旦所有元素都相同l会一路跑到数组末尾甚至越界。正确写法必须带l r限制while l r and nums[l] nums[l 1]: l 1。我的经验是凡是while内嵌while的场景内层循环一定要复述外层循环的约束条件。虽然代码会变长一点但能避免大量的边界调试时间。宁可多写几行也不要赌这里应该不会越界。4.4 双指针还是哈希表选择恐惧症怎么治遇到找两数之和这类题很多人纠结用哈希表还是双指针。我给一个简单的判断标准如果数组无序首选哈希表因为双指针依赖有序性如果数组已经有序双指针和哈希表都能做但双指针不需要额外空间。如果是三数之和并要求去重双指针优势更明显哈希表版本的去重逻辑非常繁琐。空间敏感的场景也优先双指针。绝大多数双指针解法空间复杂度是O(1)这是它很强的竞争力。面试里提一句双指针解法只需要常数级额外空间通常能加分。反向场景是你要找两个元素的下标且不能排序那哈希表更合适因为排序会丢失下标信息。4.5 去重逻辑为什么会输出重复答案去重翻车最常见的原因是只处理了一部分重复来源。以三数之和为例固定第一个数的去重、左右指针指到元素的去重必须同时处理少一个就会输出重复解。我自己的排查方法比较笨但有效先写一个纯暴力版本它能保证不遗漏答案但可能有重复然后给双指针版本加上去重逻辑最后用相同用例跑一遍对比结果集确认优化版本没有误删合法答案也没有多余重复项。还有一个小技巧去重循环如果放在找到答案之后要先跳过所有重复元素再统一移动一步。如果放在判断之前可能跳过一组还没判断过的组合。顺序写反的话错误很隐蔽不容易一眼看出来。5. 双指针刷题路线与面试表达建议5.1 三个问题快速判断能否用双指针我给自己总结了一套快速判断清单面试和刷题都适用数据是有序数组或者可以排序吗问题是否要求连续子序列、子串或链表中的特定位置暴力枚举的复杂度是否明显超出现实约束如果至少一个问题答是双指针就值得优先尝试。更抽象一点双指针适用的问题大多具有某种单调性——移动指针的过程不会让已有搜索结果退化。这个感觉可能一时说不上来但刷够一定量之后拿到题目脑子里会直接弹出几种候选模型。5.2 从易到难的练习顺序建议我推荐的顺序是先做对撞指针的两数之和与三数之和把有序数组里指针移动的节奏练熟再做快慢指针的链表判环、找链表中间节点熟悉速度差的用法然后做滑动窗口的最长无重复子串和最小覆盖子串练窗口收缩的临界处理最后挑战接雨水、盛最多水的容器这类综合题。每个类型至少做两道题做完总结一遍指针移动规律比盲目刷二三十道更有效。刷题时我会刻意不看题解先自己写一遍哪怕超时也没关系。写完暴力版之后再把暴力版优化成双指针版对比一下两个版本在哪些地方做了剪枝这个对比过程比看十篇题解都管用。因为你能亲眼看懂原来那些比较次数被什么信息省掉了也就真正理解了双指针的本质。5.3 面试现场怎么把思路讲明白面试考察的不只是代码正确还有思路讲述能力。拿到双指针题我会先开口说这道题暴力枚举会超时但数组有序所以可以用双指针然后把指针移动逻辑讲清楚重点说明为什么移动这一侧不会漏解。面试官最想听到的是那句这个移动不会影响正确性因为当前这侧已经不可能和其他元素组成目标值了。语言表达上尽量用我选择移动左指针因为当前左值太小和右侧任何值相加都小于目标而不是就移动一下左边。前者是在解释算法逻辑后者只是描述动作。提前练习这种表达方式比临时组织语言自然得多。面试里代码写不出来可以慢慢想但思路讲不清楚很难翻身。5.4 空间优势与常数取舍双指针为什么值得优先写双指针题目大多空间复杂度O(1)这是它非常突出的优势。相比之下哈希表和动态规划的空间复杂度可能是O(n)。某些场景里双指针在常数项上并不占优比如滑动窗口最坏情况下左指针走的步数等于右指针扩展的步数整体还是O(n)但实际常数可能比哈希表方案略大。如果面试官追问可以坦诚说一句双指针省空间但常数可能比哈希表方案略高。不过从我实际刷题经验看面试场景里空间优势通常比常数优势更被看重。很多双指针题的标准解就是O(1)空间你能写出来本身就比只会哈希表方案的候选人更完整。练双指针不亏。最后再分享一个我刷题阶段养成的习惯双指针题的代码普遍很短但短代码反而容易藏错误。我每次写完都会用几个特殊样例自查——空数组、全相同元素、最大最小值、两指针刚好相邻。把这些边界跑一遍九成以上的翻车都能提前拦住。双指针真正的难点不是代码本身而是你有多相信这一步可以安全跳过。把每一处安全跳过的逻辑都想通这道题才算真正吃透了。 
长河君 · 2026/10/16 14:52:02 · 阅读 1.2k 双指针算法核心逻辑与四种经典模型：从O(n²)到O(n)的优化实战
刷算法题这段时间双指针应该是我用得最频繁的一类解法。它不算某个具体算法更像是一套代码组织思路——在数组、链表、字符串这类线性结构上同时维护两个指针来遍历、比较或计算。许多一眼看去要两层循环暴力枚举的问题换成双指针后一遍扫描就能搞定时间复杂度从O(n^2)直接降到O(n)。这篇文章我把双指针的常见模型拆开讲一遍再配合几道经典算法题把边界条件和指针移动时机都说明白。适合刚开始刷题的新手也适合面试前突击双指针专项的朋友。很多人把双指针当成一堆零散技巧在背其实它背后是利用单调性减少无效枚举这一条核心逻辑。对撞指针、快慢指针、滑动窗口、分离双指针本质上只是四种不同的指针配合方式。把这层底层逻辑想明白再去看任何双指针题思路都会清晰很多。下面先从什么时候该用双指针讲起。1. 双指针能解决什么问题从适用场景到底层逻辑1.1 什么时候该往双指针上想先说我自己的判断标准。题目里如果出现有序数组连续子数组链表有环两数之和无重复子串这类关键词基本就能往双指针上靠。另一个信号是直接暴力枚举大概率超时但数据本身是线性结构、顺序关系很明显这种题用双指针往往一拍即合。我的实际操作节奏是拿到题目先花五秒钟问自己三个问题。第一数据本身是否有序或者能不能排序第二问题是否要求找一对元素、一段连续区间、链表中某个特殊位置第三暴力解的复杂度大概是多少有没有明显可以剪枝的空间如果前两个问题里有任何一个答案是第三个问题又明显超时那双指针就是我的第一优先级方案。举个例子无序数组找两数之和第一反应不直接是双指针而是先排序。排序本身O(n log n)排序之后再双指针O(n)整体可以接受。再比如判断链表里有没有环快慢双指针几乎是标准解没什么可犹豫的。双指针不挑语言、不挑平台它属于数据结构与算法基础的一部分值得好好掌握。1.2 O(n^2)到O(n)双指针到底省在哪儿这个问题我想掰开讲。以对撞指针为例数组有n个元素暴力解法枚举所有(i, j)组合需要n(n-1)/2次比较。但用左指针l和右指针r分别从两端出发每次根据当前sum与target的大小关系要么移动l要么移动r。整个过程中每个元素最多被访问两次——一次作为左指针指向它一次作为右指针指向它所以总复杂度是O(n)。快慢指针的原理也类似。普通单指针在某些场景下需要反复回头扫描快慢指针利用速度差在线性结构上交错前进整体遍历一遍就解决问题。滑动窗口则是维护窗口的左右边界右指针负责扩展左指针负责收缩整个序列也只被扫描一次。用一句不严谨但好记的话来概括双指针把盲目枚举变成了有方向的探索而这个方向来自数据结构本身的单调性。顺着这个思路理解题目比死记硬背几种子类型有用得多。2. 四种经典双指针模型一次讲透2.1 左右对撞指针有序数组的两端逼近左右对撞指针是所有模型里最好理解的。左指针从数组头部开始右指针从尾部开始根据当前计算结果的大小关系决定移动哪一侧。最经典的就是有序数组的两数之和当sum(a[l] a[r])大于target时说明右侧值太大了右指针向左移小于target时说明左侧值太小了左指针向右移。这个模型有个隐含前提——数据要有序。没有有序性移动指针就缺乏依据对撞就变成乱撞。有人会问如果数组本身无序怎么办答案很简单先排序再双指针。排序成本O(n log n)往往可以接受换来的线性扫描收益更大。见到有序数组四个字就想到对撞指针这个映射关系建议直接刻进脑子里。2.2 快慢指针链表题的主心骨快慢指针最经典的应用是链表判环。慢指针每次走一步快指针每次走两步如果有环两者一定在环内相遇。这个结论不用死记物理意义很直白快慢速度差是1在环里相当于快指针每一步靠近慢指针一步环的长度有限必然在某一步追上。除了判环快慢指针还能做不少事。找链表中间节点时快指针走两步、慢指针走一步快指针到终点时慢指针恰好到中间。删除链表倒数第n个节点时先让快指针走n步再让快慢指针同步前进快指针抵达到尾部时慢指针正好停在待删除节点的前一个位置。这几个场景基本覆盖了链表题里的高频考点练熟之后手感会好很多。2.3 滑动窗口连续子串问题的标准解法滑动窗口几乎是为连续子数组和子串问题量身定做的。右指针负责扩展窗口、覆盖新元素左指针只在不满足条件时收缩窗口。窗口内部的状态用一个set、dict或者普通变量维护窗口每一次调整后都尝试更新最优解。这个模型最关键的编写顺序是右指针移动判断当前窗口是否满足条件不满足就移动左指针收缩等到条件满足后再尝试更新答案。很多新手把更新答案放在了收缩之前导致结果永远差一点。再强调一次窗口必须是原序列中的连续片段所以删除元素永远从左侧删除不能直接抽掉中间某个值。这个细节在字符类题目里尤其致命。2.4 分离双指针两个有序序列的合并利器分离双指针常见于归并排序、合并两个有序数组、找两个有序数组的交集这类场景。两个指针各自指向不同序列比较当前指向元素的大小根据比较结果决定推进哪个指针。其实质和归并排序的核心过程一模一样。它和对撞指针最大的区别是数据源不同对撞指针处理同一个数组的两端分离双指针处理两个独立序列。实现起来不难但有个边界容易漏——其中一个序列走完后剩余元素要全部复制到结果里。这个操作漏掉的后果是合并结果少了一段而且有时候还不会立刻报错要等到用例验证才知道出了问题。模型典型场景指针方向核心前提左右对撞有序数组两数之和、三数之和相对而行数据有序快慢指针链表判环、找中间节点同向不同速链表等可循环结构滑动窗口无重复子串、最小覆盖子串同向前进连续区间问题分离双指针合并有序数组、归并排序各自推进两个序列有序3. 五道经典双指针题目实战拆解从入门到进阶3.1 两数之和 II对撞指针最典型的入门题这道题要求在有序数组中找到两个数使它们的和等于target返回下标。暴力解法是两层循环O(n^2)对撞指针写法如下def two_sum(numbers, target): l, r 0, len(numbers) - 1 while l r: s numbers[l] numbers[r] if s target: return [l 1, r 1] elif s target: l 1 else: r - 1 return [-1, -1]这个解法里最需要理解的是为什么只移动一个指针不会漏解。当sum小于target时说明当前的a[l]加上最右侧的a[r]都达不到目标那a[l]加上右侧任何一个更小的元素也必然达不到目标所以左指针可以放心右移。这就是有序性提供的剪枝依据。还有个常见误区有人觉得和太小是不是左右都要往中间动一动。答案是绝对不能同时移动两个指针。同时移动相当于跳过了l1与r的组合而这个组合可能恰好就是正确答案。对撞指针每一步只移动一侧本质上是在一个二维搜索空间中沿着一条有效的路径前进方向由大小比较决定。3.2 三数之和排序加去重的综合演练三数之和要求找出数组中所有三个数和为0的组合且不能重复。直接三重循环肯定超时标准做法是排序加双指针。先固定第一个数再在其右侧的子数组上做对撞双指针找两数之和。这里有三处细节最容易出问题第一固定的第一个数如果和上一个相同需要跳过否则会产生重复答案。第二对撞时找到一组解后l和r都要移动并且要把相邻的重复元素全部跳过才能保证下一个组合不重复。第三如果第一个数已经大于0后面的数都比它大三数和不可能为0可以直接结束循环。def three_sum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue if nums[i] 0: break l, r i 1, n - 1 while l r: s nums[i] nums[l] nums[r] if s 0: res.append([nums[i], nums[l], nums[r]]) while l r and nums[l] nums[l 1]: l 1 while l r and nums[r] nums[r - 1]: r - 1 l 1 r - 1 elif s 0: l 1 else: r - 1 return res这段代码里最妙的细节是去重的时机。找到一组解后先把左右指针移动到重复元素的最后一个位置再各走一步这样既能避开重复解又能配合外层while条件保证不越界。第二个需要留意的点是nums[i] nums[i-1]这一判断它保证固定位的首个值不重复枚举。这些细节单独看都不难组合在一起就变成了这道题最磨人的地方。3.3 最长无重复子串滑动窗口的教科书这道题要求找字符串中最长的不含重复字符的子串。暴力解法枚举所有子串并判断是否重复复杂度能到O(n^3)。滑动窗口可以做到一次遍历O(n)def length_of_longest_substring(s): seen set() l 0 ans 0 for r, ch in enumerate(s): while ch in seen: seen.remove(s[l]) l 1 seen.add(ch) ans max(ans, r - l 1) return ans这里有一个非常容易踩的坑while循环里移除的是s[l]不是ch本身。因为重复字符可能出现在窗口中间只有从左边逐步收缩才能保证窗口始终是原字符串的连续片段。如果直接remove掉ch窗口就不是一个连续区间了后面算出的长度毫无意义。我第一次写这题就在这个坑里卡了半天输出结果总是跟正确答案差一截。后来想明白滑动窗口的窗口必须语义正确删除只能从左边界进行。如果遇到窗口内大量重复的场景set的删除效率不够直观可以换成dict存储每个字符最近出现的下标左指针直接跳到max(l, dict[ch] 1)代码写起来更干净也更好解释。3.4 盛最多水的容器理解短边决定上限这道题给一组柱状高度要求选择两根柱子形成容器求最多能盛多少水。容器面积 两柱之间的宽度 x 较矮柱子的高度。暴力解法枚举所有柱对O(n^2)双指针解法是对撞def max_area(height): l, r 0, len(height) - 1 ans 0 while l r: area min(height[l], height[r]) * (r - l) ans max(ans, area) if height[l] height[r]: l 1 else: r - 1 return ans很多人理解不了为什么移动较矮的一侧就是安全的。我提供一个直观思路当前较矮柱子是height[l]那么无论右侧怎么向左移动容器高度都不可能超过height[l]因为瓶颈在左柱。此时以左柱为边界的最大可能面积是height[l]乘以当前宽度而这个上限会随着宽度缩小而递减。也就是说以这根矮柱为左边的所有情况都已经枚举到头了放弃它不会错过更大面积。反过来如果移动较高的那根柱子高度上限被矮柱锁死宽度还在减少面积只可能更小。那句移动短边本质上是因为短边决定了容器面积的天花板移动短边才有机会遇到更高的柱子来抬升天花板。3.5 接雨水双指针与动态规划的切换接雨水是双指针题目里比较难的一道。给定柱状高度求能接住的总雨水量。双指针解法的核心是当前柱子能接多少水取决于左右两侧最高柱子中较矮的那个。如果左侧最高值小于右侧最高值那当前柱子的存水量就是左最高值减去当前柱高因为右侧必然有足够高的柱子挡住雨水。def trap(height): l, r 0, len(height) - 1 left_max right_max 0 ans 0 while l r: left_max max(left_max, height[l]) right_max max(right_max, height[r]) if left_max right_max: ans left_max - height[l] l 1 else: ans right_max - height[r] r - 1 return ans这段代码维护left_max和right_max两个变量用来记录两侧遍历过程中见过的最高值。每一轮都选较矮的一侧计算雨水量再移动对应指针。我个人认为双指针版比动态规划版代码短很多但思维台阶更高。如果你刚开始刷这题建议先写动态规划版理解每列能存水取决于左右最大值中较小者这个逻辑再切换到双指针版衔接会顺很多。4. 双指针题常见的坑与排查心得4.1 指针越界所有双指针题的第一灾难双指针最容易翻车的就是数组越界。我自己总结了几条规律只要循环条件是while l r循环体里对nums[l]或nums[r]的访问就是安全的因为条件本身保证了l和r合法。但如果写成while l r循环内最后一次操作后l可能越过数组尾部后续再访问就可能崩。另一种越界出现在窗口收缩时。以最长无重复子串为例如果while ch in seen内部的逻辑写错左指针l可能一路加到超出数组范围。解决办法是收缩循环内部始终保留l r这种语义约束并且要确认每次删除的字符确实属于当前窗口。简单说双指针的每个while循环都要自己问一句这个循环靠什么停下来停下来时指针指向哪里这两个问题回答清楚越界问题基本能杜绝。4.2 指针移动时机到底先移动还是先判断这个坑在滑动窗口里尤其突出。我的习惯是先看当前状态是否需要调整再决定更新答案的顺序。两数之和里是先计算当前和再决定移动哪边最长无重复子串里是先把不满足窗口条件的字符清出去再把新字符加进来最后更新答案。这个顺序没法靠背必须理解每一步修改对状态的影响。有一个通用检查技巧把所有指针和状态变量在头脑里模拟一遍。比如右指针每走一步左指针可能连续走好几步窗口内部数据如何变化更新答案的位置是否覆盖了最优情况。动手写代码之前在注释里标出这三个动作的顺序基本不会错。4.3 死循环while条件写岔了双指针题的死循环多半是内层循环的终止条件没写对。比如三数之和里的去重循环如果写成while nums[l] nums[l 1]: l 1一旦所有元素都相同l会一路跑到数组末尾甚至越界。正确写法必须带l r限制while l r and nums[l] nums[l 1]: l 1。我的经验是凡是while内嵌while的场景内层循环一定要复述外层循环的约束条件。虽然代码会变长一点但能避免大量的边界调试时间。宁可多写几行也不要赌这里应该不会越界。4.4 双指针还是哈希表选择恐惧症怎么治遇到找两数之和这类题很多人纠结用哈希表还是双指针。我给一个简单的判断标准如果数组无序首选哈希表因为双指针依赖有序性如果数组已经有序双指针和哈希表都能做但双指针不需要额外空间。如果是三数之和并要求去重双指针优势更明显哈希表版本的去重逻辑非常繁琐。空间敏感的场景也优先双指针。绝大多数双指针解法空间复杂度是O(1)这是它很强的竞争力。面试里提一句双指针解法只需要常数级额外空间通常能加分。反向场景是你要找两个元素的下标且不能排序那哈希表更合适因为排序会丢失下标信息。4.5 去重逻辑为什么会输出重复答案去重翻车最常见的原因是只处理了一部分重复来源。以三数之和为例固定第一个数的去重、左右指针指到元素的去重必须同时处理少一个就会输出重复解。我自己的排查方法比较笨但有效先写一个纯暴力版本它能保证不遗漏答案但可能有重复然后给双指针版本加上去重逻辑最后用相同用例跑一遍对比结果集确认优化版本没有误删合法答案也没有多余重复项。还有一个小技巧去重循环如果放在找到答案之后要先跳过所有重复元素再统一移动一步。如果放在判断之前可能跳过一组还没判断过的组合。顺序写反的话错误很隐蔽不容易一眼看出来。5. 双指针刷题路线与面试表达建议5.1 三个问题快速判断能否用双指针我给自己总结了一套快速判断清单面试和刷题都适用数据是有序数组或者可以排序吗问题是否要求连续子序列、子串或链表中的特定位置暴力枚举的复杂度是否明显超出现实约束如果至少一个问题答是双指针就值得优先尝试。更抽象一点双指针适用的问题大多具有某种单调性——移动指针的过程不会让已有搜索结果退化。这个感觉可能一时说不上来但刷够一定量之后拿到题目脑子里会直接弹出几种候选模型。5.2 从易到难的练习顺序建议我推荐的顺序是先做对撞指针的两数之和与三数之和把有序数组里指针移动的节奏练熟再做快慢指针的链表判环、找链表中间节点熟悉速度差的用法然后做滑动窗口的最长无重复子串和最小覆盖子串练窗口收缩的临界处理最后挑战接雨水、盛最多水的容器这类综合题。每个类型至少做两道题做完总结一遍指针移动规律比盲目刷二三十道更有效。刷题时我会刻意不看题解先自己写一遍哪怕超时也没关系。写完暴力版之后再把暴力版优化成双指针版对比一下两个版本在哪些地方做了剪枝这个对比过程比看十篇题解都管用。因为你能亲眼看懂原来那些比较次数被什么信息省掉了也就真正理解了双指针的本质。5.3 面试现场怎么把思路讲明白面试考察的不只是代码正确还有思路讲述能力。拿到双指针题我会先开口说这道题暴力枚举会超时但数组有序所以可以用双指针然后把指针移动逻辑讲清楚重点说明为什么移动这一侧不会漏解。面试官最想听到的是那句这个移动不会影响正确性因为当前这侧已经不可能和其他元素组成目标值了。语言表达上尽量用我选择移动左指针因为当前左值太小和右侧任何值相加都小于目标而不是就移动一下左边。前者是在解释算法逻辑后者只是描述动作。提前练习这种表达方式比临时组织语言自然得多。面试里代码写不出来可以慢慢想但思路讲不清楚很难翻身。5.4 空间优势与常数取舍双指针为什么值得优先写双指针题目大多空间复杂度O(1)这是它非常突出的优势。相比之下哈希表和动态规划的空间复杂度可能是O(n)。某些场景里双指针在常数项上并不占优比如滑动窗口最坏情况下左指针走的步数等于右指针扩展的步数整体还是O(n)但实际常数可能比哈希表方案略大。如果面试官追问可以坦诚说一句双指针省空间但常数可能比哈希表方案略高。不过从我实际刷题经验看面试场景里空间优势通常比常数优势更被看重。很多双指针题的标准解就是O(1)空间你能写出来本身就比只会哈希表方案的候选人更完整。练双指针不亏。最后再分享一个我刷题阶段养成的习惯双指针题的代码普遍很短但短代码反而容易藏错误。我每次写完都会用几个特殊样例自查——空数组、全相同元素、最大最小值、两指针刚好相邻。把这些边界跑一遍九成以上的翻车都能提前拦住。双指针真正的难点不是代码本身而是你有多相信这一步可以安全跳过。把每一处安全跳过的逻辑都想通这道题才算真正吃透了。