双指针算法全解：三类套路、边界避坑与合并有序数组

1. 先说个现象为什么有人刷了100道双指针面试还是挂上周LeetCode周赛430打完群里不少人在讨论T2那道合并有序数组的题。题目本身不难但统计下来真正在十分钟内写出无bug解法的人不到一半。我看了一下讨论区发现一个很有意思的共同点不是大家不会写双指针而是大多数人只会背模板不会判断什么时候该用双指针。这恰好也是我在面试候选人时最常看到的短板。问“链表有没有环”都知道快慢指针问“有序数组里找两数之和”也都知道左右指针。但稍微变个形——比如“给你两个有序数组要求原地合并”立刻有人卡在从前往后遍历会把元素覆盖掉这个细节上。这篇文章不打算把LeetCode Top 100 Liked里所有双指针题挨个讲一遍那不现实也容易变成题解流水账。我按照自己刷题带人这些年的经验把双指针拆成几个真正有用的维度它到底是什么、怎么一眼识别、三类核心套路的代码骨架长什么样、最容易踩的边界坑在哪里。文末还会专门讲一道和“Java合并有序数组”热搜词相关的题把从后往前合并这个技巧彻底说透。无论你是刚开始刷题的新手还是已经刷了大几十题但总觉得双指针“会但不熟”的进阶选手这篇文章应该都能给你一些能直接落到代码里的东西。2. 双指针不是一招而是三类看家本领很多人把双指针理解成“两个下标在数组上跑来跑去”这么想不能算错但太粗了。实际刷题和面试里双指针至少可以拆成三个完全不同的变体每种变体的适用场景、代码骨架、边界敏感点都不一样。2.1 左右对撞指针最经典也最好认左右对撞指针就是两个指针分别从数组两端出发根据条件决定谁往中间挪直到两个指针相遇。它的核心前提是数组天然有序或者经过排序后可以有序。典型题目包括两数之和有序数组版三数之和盛最多水的容器接雨水部分解法验证回文串反转数组这类的代码骨架非常固定left, right 0, len(nums) - 1 while left right: if condition(nums[left], nums[right]): left 1 else: right - 1关键判断都在这个condition里。比如两数之和condition就是nums[left] nums[right]和目标值的大小关系。盛最多水的容器condition就是左板和右板谁矮矮的那边往中间挪。左右对撞指针最容易被忽略的一点是它依赖数据的单调性。如果数组本身无序你必须先排序。但排序会丢失下标信息所以如果题目要求返回原始下标左右对撞就走不通了得换哈希表。这个我在面试里见过太多人踩雷——一上来就排序排完了发现要返回原下标整个人就懵了。2.2 快慢指针处理链表和原地去重的利器快慢指针一个走的快、一个走的慢两者之间存在速度差或出发位置差。它的典型应用场景有两类第一类是链表问题。判断链表是否有环快指针每次走两步慢指针每次走一步有环必相遇、寻找链表中间节点快指针到末尾时慢指针正好在中点、寻找链表的倒数第K个节点快指针先走K步然后同步走。第二类是原地数组操作。比如移除元素、移除有序数组中的重复项、移动零。这类题的慢指针指向“新数组的写入位置”快指针负责扫描原数组发现符合条件的元素就写入慢指针的位置然后慢指针前进。快慢指针的代码骨架以移除元素为例slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这个模式特别值得留意。它在LeetCode上的难度标注经常是“简单”但实际面试里能把slow的语义解释清楚的人并不多。slow不是“当前遍历到哪”而是“下一个合法元素应该放哪”。理解到这一层移除重复项、移动零这类题就全通了。2.3 滑动窗口双指针的高级形态滑动窗口本质上也是两个指针只是两个指针始终维护一个窗口区间窗口的左边界和右边界根据条件动态调整。它解决的问题几乎都有一个共同特征连续子数组、连续子串。典型题目包括无重复字符的最长子串长度最小的子数组最小覆盖子串字符串排列水果成篮滑动窗口的代码骨架比前两类复杂一些但结构非常固定left 0 for right in range(len(s)): # 1. 右指针扩张窗口更新窗口内状态 # 2. 判断窗口是否满足条件 while 窗口不满足条件: # 3. 左指针收缩窗口更新窗口内状态 left 1 # 4. 此时窗口满足条件更新答案滑动窗口容易写错的地方是“窗口内状态”的维护。字符串类题目需要维护字符频率表数组类题目可能只需要维护一个sum值。很多人写while条件的时候边界差一个就爆栈这个我在后面专门讲。3. 怎么识别一道题该用双指针两条判断主线我刷了几年题也带过不少人发现高手和普通选手最大的差距不在代码量在于做题前的分类速度。普通选手拿到题就开始想解法高手会先花三十秒问自己三个问题数据是有序的吗求的是连续区间还是离散组合时间复杂度有没有硬性要求具体到双指针我总结了两条判断主线。3.1 主线一数据有序或可排序——左右对撞的强烈信号题目里出现“有序数组”“排序后”“两数之和”“三数之和”“水容器”这些关键词时优先考虑左右对撞。更准确地说只要题目给了你一个数组并且答案是其中若干元素的组合且对顺序没有要求你都可以尝试排序加双指针的路线。举个例子三数之和就是两数之和的升级版。固定第一个数之后剩下的两个数就变成了有序数组里的两数之和用左右对撞一次搞定。这也是为什么Top 100 Liked里三数之和几乎是双指针必刷题。但要注意一个反向判断如果题目要求返回原始下标或者数据量大到排序本身就会超时左右对撞就不合适了。这时候哈希表往往是更好的选择。3.2 主线二连续区间、子串子数组——滑动窗口的强烈信号题目里出现“连续子数组”“子串”“最长”“最短”“包含某些字符”这些关键词时优先考虑滑动窗口。滑动窗口解决的核心问题是在连续区间上求满足条件的最优子区间。这里有个容易混淆的点。有些题看起来是“子数组”但实际要求不连续那就不能用滑动窗口。比如“和为K的子数组”这道题它求的是连续子数组但数据可能是负数所以滑动窗口的单调性被破坏了得用前缀和加哈希表。所以拿到题先确认区间收缩时窗口内状态的变化是不是单调的。如果加一个负数会让sum变小那left右移时sum可能变大也可能变小滑动窗口就不成立了。快慢指针的判断相对简单链表问题几乎都可以想想快慢指针数组原地操作、要求空间复杂度O(1)的基本都是快慢指针的活。下面这个表是我自己刷题时用的判断参考分享出来供大家对照题目特征首选方案代表题目有序数组选若干元素组成目标值左右对撞两数之和、三数之和两个边界围成的面积/容量最大左右对撞盛最多水的容器、接雨水链表成环/找中点/倒数第K节点快慢指针环形链表、链表的中间结点数组原地去重/移除元素/O(1)空间快慢指针移除元素、删除有序数组重复项连续子串/子数组最优解滑动窗口无重复字符的最长子串、最小覆盖子串子数组和为K含负数前缀和哈希表和为K的子数组4. 三类题型的代码骨架和避坑要点有了识别方法接下来就是动手写。我把三类双指针的核心代码骨架和最容易出错的点分别展开说一下。为了让你有真实刷题的代入感每类我都会配一道Top 100 Liked里的代表题。4.1 左右对撞骨架从“盛最多水的容器”看收缩逻辑盛最多水的容器这道题题目是给一个高度数组找到两条线跟x轴构成容器使得容器能装最多水。很多人的第一反应是两层循环暴力解这当然可以但会超时。用双指针的正确思路是左右指针指向数组两端计算当前面积然后移动较短的那根指针。为什么移动短的而不是长的因为面积由短边决定移动长边只会让底变窄面积不可能变大移动短边则有可能遇到更高的边让面积有机会变大。def maxArea(height): left, right 0, len(height) - 1 max_area 0 while left right: width right - left if height[left] height[right]: area height[left] * width left 1 else: area height[right] * width right - 1 max_area max(max_area, area) return max_area这个解法的正确性证明依赖两个关键点一是面积受短边限制二是移动短边不会漏掉最优解。面试时如果能把这个逻辑讲清楚基本就过关了。这里有个常见的边界错误两个指针相遇时要不要再算一次面积不需要。因为宽度为0面积必为0不影响结果。但如果你把循环条件写成left right相遇时height[left]和height[right]指向同一个元素面积算出来是0也不报错只是多了次无意义的计算。从代码整洁度讲while left right是更标准的写法。4.2 快慢指针骨架从“移动零”看原地操作的写法移动零这道题要求把数组里所有0移到末尾同时保持非零元素的相对顺序。题目明确要求原地操作这就是快慢指针的典型信号。我的写法是def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1这里用了交换而不是直接赋值好处是能自动把0“挤”到后面。如果你写成nums[slow] nums[fast]最后还得补一轮循环把slow之后的位置全置0多一步不说还容易漏。快慢指针类题最容易犯的错是把slow和fast的关系搞混。fast是探索者负责往前扫描slow是记录者只负责标记下一个合法的写入位置。任何时候都不要让slow越过fast否则你会把还没扫描的元素覆盖掉。4.3 滑动窗口骨架从“无重复字符的最长子串”看窗口维护这道题的题意很直白给定一个字符串找出不含重复字符的最长子串的长度。凡是“子串最长/最短”优先滑动窗口。窗口的维护逻辑是右指针不断向右扩展把新字符加入窗口一旦发现窗口内有重复字符左指针右移直到重复问题被解决。def lengthOfLongestSubstring(s): left 0 max_len 0 char_set set() for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left 1 char_set.add(s[right]) max_len max(max_len, right - left 1) return max_len这个写法用的是最朴素的set维护窗口内字符。每次遇到重复时左指针一步步往右挪一边挪一边从set里删字符。理论上可以优化成用字典记录每个字符最后出现的位置左指针可以直接跳到该跳的位置但朴素的写法也足够通过所有测试用例而且更好理解。滑动窗口的坑主要在两个地方。第一个坑先判断重复再添加还是先添加再判断。上面的写法是先while处理掉重复再加新字符顺序不能反。第二个坑更新答案的时机。无重复字符这道题里答案是每次右指针扩展后都要尝试更新但“最小覆盖子串”那道题答案是窗口收缩到仍满足条件的最小值时更新。所以别把答案更新语句的位置背死要理解它应该放在“窗口满足条件的时刻”。5. 合并有序数组从后往前合并的思路详解现在专门说说热搜词里反复出现的“合并有序数组”。这道题在LeetCode上有两个版本一个是合并两个有序链表另一个是合并两个有序数组要求原地合并到第一个数组里。后者在面试里出现频率极高而且很多人第一次写都会栽在“从前往后合并会覆盖元素”这个坑上。题目大致长这样给你两个有序整数数组nums1和nums2nums1有足够的空间长度是mn来容纳nums2。请把nums2合并到nums1中使nums1成为一个有序数组。其中nums1的有效元素个数是mnums2的有效元素个数是n。如果从前往后合并问题很明显把nums2的小元素插入到nums1的前部时nums1里还没比较的元素会被覆盖。解决办法就是从后往前合并。既然两个数组都是有序的那么最大的元素一定在nums1的第m-1位和nums2的第n-1位之间。我们把两个指针分别指向nums1有效元素的末尾和nums2的末尾比较大小大的放nums1的末尾第mn-1位然后指针前移。def merge(nums1, m, nums2, n): p1 m - 1 # nums1 有效元素末尾 p2 n - 1 # nums2 末尾 p m n - 1 # nums1 合并后的末尾 while p2 0: # 只需处理 nums2 还有剩余的情况 if p1 0 and nums1[p1] nums2[p2]: nums1[p] nums1[p1] p1 - 1 else: nums1[p] nums2[p2] p2 - 1 p - 1 return nums1这段代码最妙的地方在于循环条件只检查p2 0。因为如果nums2已经全部合并完毕nums1剩下的前半部分本身就是有序的不用再动。这个逻辑很多人第一次看会愣一下想“nums1还没处理完怎么办”其实完全不用处理。这个“从后往前”的思路不仅能用在合并有序数组上很多原地操作的题目都能派上用场。比如“把字符串里的空格替换成%20”这类题如果题目要求原地操作也是从后往前扩。我还遇到过面试官把这道题改一下不给你nums1的额外空间要求合并后返回一个新数组。那就退化成了归并排序的merge过程用两个指针从头往后扫谁小先放谁最后把剩余部分接上。这个做法简单很多但思路里同样藏着双指针的骨架。6. 双指针代码的几个隐藏大坑写完代码通过测试用例不代表这道题你真的会了。我见过太多人在面试里手写双指针时代码逻辑全对但被面试官追问几个边界case就露馅。这里列几个我踩过、也看别人踩过的坑统一整理出来。6.1 循环不变量弄错while边界是最大杀手左右对撞的循环条件到底是left right还是left right这取决于你对“循环不变量”的定义。如果循环里每一次都要处理nums[left]和nums[right]这对组合比如两数之和、三数之和那么left right就够了因为left等于right时两个指针指向同一个元素没有“两个数”可言处理了也没有意义。但如果是二分查找那种在数组中找目标的场景目标是可能落在某一个下标上的这时就要用left right否则会漏掉left等于right时的那次检查。这个区别一定要理解透彻不要死记硬背。面试时能说出“我的循环不变量是什么所以条件为什么这么写”是非常加分的。6.2 快慢指针的速度差不是随便定的链表判环为什么快指针走两步、慢指针走一步而不是快指针走三步四步因为要保证快慢指针的相对速度差为1这样它们在环里一定能相遇。如果快指针走三步慢指针走一步相对速度是2那么当它们之间的距离是奇数时有可能永远错过。当然实际上只要相对速度差是1无论初始距离是多少都一定会在有限步内相遇。相对速度差大于1时则有可能跳过去。所以标准答案就是快走两步、慢走一步。如果有人问“快能不能走四步”你可以回答“能走但没必要而且可能死循环”。6.3 滑动窗口的收缩时机不对结果必然错滑动窗口题里最经典的错误是在窗口不满足条件时没有收缩直接更新答案或者收缩过头把本来合法的解也丢了。以“长度最小的子数组”为例这道题求的是和≥target的最短连续子数组。很多人会写成for right in range(len(nums)): cur_sum nums[right] while cur_sum target: ans min(ans, right - left 1) cur_sum - nums[left] left 1这个写法是对的但要注意答案更新的位置——它是在while收缩窗口的循环体里也就是“窗口刚刚满足条件”的时候。如果你把它挪到while外面更新出来的可能是已经不满足条件的窗口长度答案就错了。6.4 忘记考虑“排序破坏下标”的连锁反应前面提到过左右对撞依赖有序性但排序会破坏数组元素的下标。如果题目要求返回的是元素本身的值排序没问题如果要求返回下标就麻烦了。解决办法有两种第一种是不排序改用哈希表记录值和下标的映射这就是经典的Two Sum解法第二种是创建一个带有原下标的结构体或元组数组排序时带着下标一起排。第二种在面试里更显功底因为它展示了你对数据结构的理解和应用。遇到这类问题建议在动笔之前先明确一点这道题最终要返回的是值、下标、还是个数这决定了你能不能走“排序双指针”这条路。7. 刷题路线建议Top 100 双指针题怎么排优先级最后聊聊实操层面的刷题顺序。LeetCode Top 100 Liked里双指针相关的题大概有十几道按照从易到难、从单一到综合的顺序我建议这样排第一梯队入门建立双指针直觉两数之和有序数组版或哈希表版都做一遍移除元素移动零反转字符串验证回文串第二梯队核心套路掌握三数之和盛最多水的容器无重复字符的最长子串删除有序数组中的重复项合并两个有序数组就是上面说的那题第三梯队进阶挑战综合运用接雨水对撞指针动态规划两种解法都搞懂最小覆盖子串滑动窗口最难的模板题环形链表快慢指针的经典应用链表的中间结点我的建议是第一梯队每道题控制在20分钟内做不出来就看题解看懂后合上答案自己默写一遍。第二梯队每道题控制在40分钟内要求能讲清楚为什么用双指针而不是其他方法。第三梯队不要求全部独立做出来但一定要能看懂题解并且能复述整个算法的正确性证明。刷题过程中有一个特别重要的习惯每道题做完后用一句话总结这道题考的是什么套路。比如“盛最多水的容器左右对撞短边收缩”“最小覆盖子串滑动窗口字符频率计数”。积累到一定量之后你会发现拿到新题时自动就能把它映射到已知的套路框架里这就是所谓的题感。我在实际带人的过程中发现那些进步快的人往往不是刷得最多的而是总结得最勤快的。双指针这个专题尤其如此——题量不大但套路固定、边界陷阱集中非常适合用来训练“识别题目模式”的能力。这个能力一旦建立起来不光是双指针后面学到二分、动态规划、回溯都会轻松很多。8. 最后再分享一个小技巧关于双指针我最后想额外聊一个容易被忽略的细节和性能有关。有些题你用双指针写完能过测试但面试官会追问一句“能不能优化空间复杂度”。比如三数之和很多人会额外开一个set用来去重这样空间复杂度就不是O(1)了。实际上双指针解法里只要加上“跳过重复元素”的逻辑就可以做到不用set而且结果不重。具体做法是外层循环固定第一个数时如果当前数和上一个数相同直接跳过内层双指针找到一组解后left和right也各自跳过所有重复元素再继续移动。这个优化能把你从“被面试官追问”的境地拯救出来而且代码改动量很小。# 三数之和中去重的关键代码片段 for i in range(len(nums)): if i 0 and nums[i] nums[i-1]: continue left, right i 1, len(nums) - 1 while left right: total nums[i] nums[left] nums[right] if total 0: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 elif total 0: left 1 else: right - 1这个小技巧在工作里也很有用。我处理过一些业务数据去重的场景原理跟这个一模一样——先排序然后用指针在相邻的重复元素上做跳跃避免用哈希集合占额外内存。从刷题到工作这个模式我用了很多年很少失手。双指针专题讲到这里差不多就完整了。从识别套路到代码骨架从边界避坑到刷题顺序希望这篇文章能帮你省下一些自己摸索的时间。如果看完之后你能动手把上面提到的代码骨架默写一遍再对着一两道真题跑通那这个专题基本就稳了。剩下的就是练习量的问题了。