1. 为什么双指针敢叫“优选算法”1.1 暴力解法的瓶颈到底在哪里先聊点实际的。你去翻任何一家公司的算法题库数组、链表、字符串这三类题型里双指针是出场率最高的解法之一。为什么因为它解决的是一个非常痛的问题暴力穷举太慢了。就拿最经典的两数之和来说给一个数组找出两个数让它们的和等于目标值。没有经验的人第一反应是嵌套两层循环外层固定一个数内层遍历剩下的数判断两个数之和是否等于目标值。这个做法时间复杂度是O(n²)数组长度一上几千性能就肉眼可见地拉胯。而你一旦把数组排好序用双指针从两头往中间走一趟就能搞定时间复杂度直接降到O(n)。这就是双指针的第一个价值——把“嵌套遍历”降维成“线性扫描”。有人可能会问那不就是把排序的时间也加上去了吗排序O(n log n)还是比O(n²)快了一个量级。而且很多场景下数据本来就是有序的比如下面的“有效三角形的个数”那道题排序几乎是标配。1.2 双指针到底“省”掉了什么要理解双指针为什么高效得先搞清楚暴力的代价在哪。两层循环之所以慢是因为它做了大量无用功。很多组合根本不需要判断你却都算了一遍。双指针的核心逻辑是通过两个指针的移动把“不可能成立”的区间直接排除掉。它不跟你硬碰硬地去穷举每个组合而是利用数据本身的规律比如单调性把待检查的范围一点点“剪掉”。这种思想本质上叫“剪枝”只不过剪得非常优雅——指针每动一次就排除掉一整片候选区域。这就像排查一个楼里的故障电梯。暴力做法是每一层都停下来、每一部电梯都试一遍。双指针的做法则是从两头分别排查左边那个指针告诉你“上半层已经排除了”右边那个指针告诉你“下半层已经排除了”很快就把中间那个可疑区域锁定了。1.3 什么时候该想到双指针这是新手最容易卡住的地方题目倒是看懂了就是不知道用哪个套路。根据我刷了数百道题的体感当题目出现这几个信号时优先想双指针第一个信号输入是一个数组或链表要求找两个元素的关系。比如找两个数的和、积、差满足某个条件极大概率是左右指针的活。第二个信号要求原地修改数组并且要保持某种相对顺序。比如把0移到末尾、把奇数移到前面、去除重复元素。这种题让新写一个数组很简单难就难在“原地”而双指针尤其是快慢指针天生就是干这个的。第三个信号链表中要判断有没有环、要找环的入口、要找倒数第K个节点。这是快慢指针的经典主场。第四个信号连续子数组、子串相关的问题。比如最长无重复子串、长度最小的子数组这类属于同向双指针也就是大家常说的“滑动窗口”。从广义上说滑动窗口也是双指针的一种形态。这四种信号覆盖了你日常刷题中大概三成到四成的题目。把这套框架先刻在脑子里碰到题目先往里套一套很多题你就知道方向了。2. 双指针的两张面孔左右指针与快慢指针2.1 左右指针从两端向中间夹逼左右指针也叫“对撞指针”它最常见的应用前提是数组有序。两个指针初始分别指向数组的第一个元素和最后一个元素然后根据当前两个指针指向的值的和或者其他关系与目标值的比较结果决定是移动左指针还是右指针。以两数之和为例数组排好序后如果nums[left] nums[right] target说明左边的数太小了怎么移动右指针都没用因为右边已经是最大的了只有把左指针往右挪一位让左值变大一点才有机会让总和变大。反过来如果和大于target就把右指针往左挪。整个过程中每一次比较都能排除一整条扫描线所以看起来像是“夹逼”一样把答案逼出来。这里有个关键细节左指针和右指针能不能相遇大多数左右指针题目要求找两个不同的元素所以循环条件通常是left right。如果允许同一个元素用两次那条件就要改成left right。别小看这个等于号很多边界问题都出在这。2.2 快慢指针一个跑得快一个跑得慢快慢指针的思路就更有意思了——让两个指针以不同的速度遍历同一个序列。最经典的应用是判断链表是否有环。你想象两个人在一条环形跑道上跑步一个快一个慢。如果跑道是封闭的环那么快的人总会在某一圈追上慢的人如果跑道是直的、有尽头的快的人只会先到达终点两人永远不会相遇。所以只要快指针在移动过程中和慢指针指向了同一个节点就说明链表里有环。快慢指针还有很多变体。比如找链表的中间节点快指针每次走两步慢指针每次走一步快指针走到末尾时慢指针正好走到中间。再比如有序数组去重快指针负责在前面探路遇到不重复的元素就把它写到慢指针指向的位置。这种情况下快慢指针更像一个“读指针”和一个“写指针”——一个负责扫描原数据一个负责记录有效结果。2.3 滑动窗口同向双指针的经典形态严格来说滑动窗口是双指针的一个分支但它太常用了值得单独说一句。它的两个指针都往同一个方向移动但是维护的区间长度是动态变化的。比如求“无重复字符的最长子串”右指针不断把新字符纳入窗口左指针在发现重复字符时收缩窗口。整个过程里右指针控制“扩张”左指针控制“收缩”两者一起把窗口在整个字符串上“滑”过去每个字符最多进一次出一次时间复杂度O(n)。所以你在学习双指针的时候不要把它理解为一种固定的代码模板而是把它理解为一种区间维护的策略——用两个指针相对灵活地圈定一个范围然后在这个范围上做计算。3. 经典题目拆解从“会背模板”到“会推导”这一部分我用几道题把双指针的常用场景挨个过一遍。这些题都是我反复讲过很多遍的从最简单的开始逐渐增加难度。我建议你跟着题目自己写一遍不要只是看。3.1 题目一移动零左右指针入门题目给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。要求原地操作不复制数组。解法思路这个题用快慢指针这里更像是一个“读写指针”就能优雅解决。我们可以维护两个指针一个dest指向“已处理区间中最后一个非零元素的下一个位置”一个cur负责遍历整个数组。cur每遇到一个非零元素就把它写到dest指向的位置然后dest往后挪一位。等cur遍历完整个数组[0, dest)区间存放的就是所有非零元素的相对顺序排列剩下的位置直接补0即可。class Solution { public: void moveZeroes(vectorint nums) { int dest 0; int n nums.size(); for (int cur 0; cur n; cur) { if (nums[cur] ! 0) { nums[dest] nums[cur]; } } for (int i dest; i n; i) { nums[i] 0; } } };注意看这里我们用cur做读指针dest做写指针。cur扫描到的非零元素被搬运到前面覆盖掉那些已经没用的位置。这个思路不需要复杂的交换逻辑代码非常简洁。时间复杂度O(n)空间复杂度O(1)。这道题的价值不在于难而在于让你熟悉“读写指针”这个模式。后面很多原地修改数组的题都是这个思路的微调。3.2 题目二复写零快慢指针进阶题目给定一个固定长度的数组arr将数组中的每个0复写一遍将其余元素向右平移。注意不要超出数组长度。要求原地操作。这个题比移动零上了一个台阶。如果从前往后扫遇到0就在前面插入一个0后面的所有元素都要整体往后挪时间复杂度直接炸到O(n²)。现场写代码很容易想到这一步然后卡住不知道怎么优化。正确解法分两步第一步先找到“最后一个会被保留的元素”。这个怎么找呢用一个哨兵指针cur遍历原数组同时用一个dest指针记录“如果复写0最终会被占到的位置”。遍历过程中如果arr[cur]是0dest就加2否则加1。当dest n - 1时停止遍历。此时cur指向的就是最后被保留的元素位置。这里有个容易翻车的边界如果最后恰好是0复写完越界——比如数组长度是5最后一个有效元素是0复写时会占用第6个位置超出了数组长度。这种情况需要特殊处理直接把数组最后一个位置写成0然后cur回退一位dest回退两位。第二步从cur位置开始从后往前填写数组。为什么要逆序因为从前往后会覆盖掉还没读到的元素。逆序复制时如果当前元素是0就连续写两个0否则只写一个原值。这个逆序过程有点像一个反向的快慢指针非常巧妙。class Solution { public: void duplicateZeros(vectorint arr) { int n arr.size(); int cur 0, dest -1; // 找最后一个保留元素 while (cur n) { if (arr[cur] 0) dest 2; else dest 1; if (dest n - 1) break; cur; } // 处理边界最后一个元素是0复写完越界 if (dest n) { arr[n - 1] 0; dest n - 2; cur--; } // 逆序填充 while (cur 0) { if (arr[cur] ! 0) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };这个题的难点在于你不仅要找到双指针的移动方式还要处理逆序复制中的边界条件。我的经验是处理这类边界时用具体的例子在纸上走一遍比如[1, 0, 2, 3, 0, 4, 5, 0]模拟到最后越界的情况你就明白为什么要加那个if (dest n)的特殊判断了。3.3 题目三快乐数快慢指针判断循环题目对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为1或者无限循环但始终变不到1。判断这个数是不是快乐数。这个题和链表有环的判断逻辑一模一样。你仔细品数位平方和的过程本质上就是一个状态转移函数。从n出发不断计算“下一个数”如果某个时刻到了1就说明是快乐数如果永远到不了1那就一定进入了某个循环。怎么高效地判断是否进入循环不用额外开哈希表记录出现过的数直接用快慢指针。慢指针每次算一步快指针每次算两步。如果存在循环快指针一定会在某个时刻追上慢指针如果不存在循环到达了1快指针会先变为1然后一直停留在1。当快慢指针相遇时如果相遇点的值是1则说明是快乐数否则就说明进入了循环。class Solution { public: int bitSum(int n) { int sum 0; while (n) { int t n % 10; sum t * t; n / 10; } return sum; } bool isHappy(int n) { int slow n, fast bitSum(n); while (slow ! fast) { slow bitSum(slow); fast bitSum(bitSum(fast)); } return slow 1; } };你可能会想这不就是链表判环吗为啥套到数字上也能用因为状态转移图本质上就是一个隐式链表——每个状态指向唯一的下一个状态。快乐数的状态空间虽然不像链表那样显式存在但逻辑结构完全一样。这就是算法的奇妙之处把不同领域的题抽象成同一个模型。3.4 题目四盛最多水的容器对撞指针经典题目给定一个长度为n的整数数组height数组中的每个元素代表一个垂直线的高度。找出其中的两条线使它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。这个题暴力做法是枚举所有下标对计算面积取最大。但细心观察会发现面积 高度较小的那条边 * 宽度所以面积由短板决定。用对撞指针初始时左指针指向最左端右指针指向最右端此时宽度最大。计算出当前面积并更新答案。然后移动较短的那条边向内移动因为如果移动较长的那条边宽度变小了但是容器的高度和原来一样面积只会更小而移动较短的那条边虽然宽度变小但有可能遇到更高的柱子使高度变大面积才有机会变大。class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int v (right - left) * min(height[left], height[right]); ans max(ans, v); if (height[left] height[right]) left; else right--; } return ans; } };这个算法的正确性本质上依赖一个很朴素的观察容器的最大容量不会超过那个“狭小的短板”所限制的范围。在移动指针的过程中我们其实是在做一件事枚举所有可能的“最优解候选”——那些可能成为短板的柱子。其余的柱子组合不需要考虑因为它们的高度受限于短板无论如何不会超过已经计算过的某个面积。很多人在面试的时候能背出“移动短的那条边”这个结论但被问到“为什么移动长的边就不行”时就卡壳了。这个题你一定要把推导过程想清楚不要只背结论。3.5 题目五有效三角形的个数排序 对撞指针题目给定一个包含非负整数的数组nums返回其中可以组成三角形三条边的三元组个数。组成三角形的条件是任意两边之和大于第三边。如果我们对数组排序然后固定最大的那条边那么只需要在剩下的数中找两个数使它们的和大于这个最大边即可。具体做法先排序。然后从数组末尾开始固定最大边用双指针在[0, i-1]区间内找两个数。左指针指向0右指针指向i-1。如果nums[left] nums[right] nums[i]说明left到right-1之间所有数跟right组合都能与nums[i]构成三角形因为排序后nums[left]是最小值它加起来都能满足条件更大的数也一定能满足。此时答案增加right - left个组合然后右指针左移一位继续比较。如果nums[left] nums[right] nums[i]说明左边的数太小了怎么搭配都不够所以左指针右移一位尝试更大一点的数。class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(); if (n 3) return 0; sort(nums.begin(), nums.end()); int ans 0; for (int i n - 1; i 2; i--) { int left 0, right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { ans right - left; right--; } else { left; } } } return ans; } };这个题里i从大到小的外循环加上内部的双指针总时间复杂度是O(n²)。你会看到双指针在这里真正发挥了“批量判断”的作用——它把内层的找数过程从O(n²)降到了O(n)整个问题从O(n³)降到了O(n²)。这是双指针在大数据量场景下最有价值的地方它可以一次性排除一片连续的区间而不是一个个地判断。4. 常见问题与排查技巧实录4.1 最容易翻车的边界条件我见过太多人在双指针上栽跟头翻来翻去无非这么几个原因循环条件写错。左右指针的循环条件到底是left right还是left right核心看的是“两个指针指向同一个元素时这个元素还有没有意义”。如果题目要求找两个不同的元素那left right就够了如果允许重复使用同一个位置才用。写代码前先问自己一句指针相遇时这个元素还能不能参与计算移动指针时越界。比如你判断height[left] height[right]之后执行left一旦数组只有两个元素这个操作可能让left变成right循环条件立刻失效。所以在循环体内移动指针时要在脑中过一遍“如果这是最后一轮循环我移动完之后会不会越界”。快慢指针步数没对齐。快指针走两步时要确保fast和fast-next都不是空指针否则会解引用空指针。这个在链表中非常常见写的时候先判空再走。死循环。有时候你想移动指针但是条件不满足两个指针谁也动不了就死循环了。遇到这种情况打印每一轮的left、right和当前计算结果看看模型是不是出了问题。4.2 一个通用的调试思路纸上走一遍我强烈建议你拿到任何一道双指针题先在草稿纸上画一个数组下标图。把左指针标成L右指针标成R然后一步步模拟指针移动的过程。走完一轮你就知道这个算法是否符合预期。我知道这看起来很笨但请相信我很多看起来高深的算法题卡住的根本原因不是思路不对而是模拟过程不够细致。特别是涉及边界处理时纸上推演一遍错误就能暴露出来。比起在代码里打日志来回试这个笨办法效率反而高。4.3 识别双指针题型的思维模型速查表最后整理一个我自己总结的速查表把你常见的场景和对应的双指针类型列在一起方便你刷题时对照题目特征优先尝试的双指针类型典型复杂度有序数组找两个元素满足某种关系左右对撞指针O(n)无序数组但排序后可变成上述问题排序 左右对撞指针O(n log n)原地修改数组保持相对顺序快慢指针读写指针O(n)判断链表中是否有环/找环入口快慢指针速度差O(n)找链表中点/倒数第K个节点快慢指针拉开距离O(n)连续子数组/子串有窗口约束同向双指针滑动窗口O(n)从后往前填充数组逆序双指针/哨兵指针O(n)你把这几个场景记熟了再碰到新题时第一反应就不会是“这个是啥”而是“这题和哪个已知类型最像”。算法学习的路径本质上就是这样把陌生问题映射到你已经掌握的模型上。双指针这块内容刷题量不需要太大把上面这几道题吃透再自己找几道同类型的巩固一遍基本就稳了。我个人练下来最大的体会是双指针的高效靠的是对问题结构的洞察而不是技巧本身。你多问自己几次“为什么这道题能优化到这个程度”比多刷十道题都管用。 
长河君 · 2026/9/9 2:19:26 · 阅读 1.2k 双指针优选算法：左右指针、快慢指针与滑动窗口实战
1. 为什么双指针敢叫“优选算法”1.1 暴力解法的瓶颈到底在哪里先聊点实际的。你去翻任何一家公司的算法题库数组、链表、字符串这三类题型里双指针是出场率最高的解法之一。为什么因为它解决的是一个非常痛的问题暴力穷举太慢了。就拿最经典的两数之和来说给一个数组找出两个数让它们的和等于目标值。没有经验的人第一反应是嵌套两层循环外层固定一个数内层遍历剩下的数判断两个数之和是否等于目标值。这个做法时间复杂度是O(n²)数组长度一上几千性能就肉眼可见地拉胯。而你一旦把数组排好序用双指针从两头往中间走一趟就能搞定时间复杂度直接降到O(n)。这就是双指针的第一个价值——把“嵌套遍历”降维成“线性扫描”。有人可能会问那不就是把排序的时间也加上去了吗排序O(n log n)还是比O(n²)快了一个量级。而且很多场景下数据本来就是有序的比如下面的“有效三角形的个数”那道题排序几乎是标配。1.2 双指针到底“省”掉了什么要理解双指针为什么高效得先搞清楚暴力的代价在哪。两层循环之所以慢是因为它做了大量无用功。很多组合根本不需要判断你却都算了一遍。双指针的核心逻辑是通过两个指针的移动把“不可能成立”的区间直接排除掉。它不跟你硬碰硬地去穷举每个组合而是利用数据本身的规律比如单调性把待检查的范围一点点“剪掉”。这种思想本质上叫“剪枝”只不过剪得非常优雅——指针每动一次就排除掉一整片候选区域。这就像排查一个楼里的故障电梯。暴力做法是每一层都停下来、每一部电梯都试一遍。双指针的做法则是从两头分别排查左边那个指针告诉你“上半层已经排除了”右边那个指针告诉你“下半层已经排除了”很快就把中间那个可疑区域锁定了。1.3 什么时候该想到双指针这是新手最容易卡住的地方题目倒是看懂了就是不知道用哪个套路。根据我刷了数百道题的体感当题目出现这几个信号时优先想双指针第一个信号输入是一个数组或链表要求找两个元素的关系。比如找两个数的和、积、差满足某个条件极大概率是左右指针的活。第二个信号要求原地修改数组并且要保持某种相对顺序。比如把0移到末尾、把奇数移到前面、去除重复元素。这种题让新写一个数组很简单难就难在“原地”而双指针尤其是快慢指针天生就是干这个的。第三个信号链表中要判断有没有环、要找环的入口、要找倒数第K个节点。这是快慢指针的经典主场。第四个信号连续子数组、子串相关的问题。比如最长无重复子串、长度最小的子数组这类属于同向双指针也就是大家常说的“滑动窗口”。从广义上说滑动窗口也是双指针的一种形态。这四种信号覆盖了你日常刷题中大概三成到四成的题目。把这套框架先刻在脑子里碰到题目先往里套一套很多题你就知道方向了。2. 双指针的两张面孔左右指针与快慢指针2.1 左右指针从两端向中间夹逼左右指针也叫“对撞指针”它最常见的应用前提是数组有序。两个指针初始分别指向数组的第一个元素和最后一个元素然后根据当前两个指针指向的值的和或者其他关系与目标值的比较结果决定是移动左指针还是右指针。以两数之和为例数组排好序后如果nums[left] nums[right] target说明左边的数太小了怎么移动右指针都没用因为右边已经是最大的了只有把左指针往右挪一位让左值变大一点才有机会让总和变大。反过来如果和大于target就把右指针往左挪。整个过程中每一次比较都能排除一整条扫描线所以看起来像是“夹逼”一样把答案逼出来。这里有个关键细节左指针和右指针能不能相遇大多数左右指针题目要求找两个不同的元素所以循环条件通常是left right。如果允许同一个元素用两次那条件就要改成left right。别小看这个等于号很多边界问题都出在这。2.2 快慢指针一个跑得快一个跑得慢快慢指针的思路就更有意思了——让两个指针以不同的速度遍历同一个序列。最经典的应用是判断链表是否有环。你想象两个人在一条环形跑道上跑步一个快一个慢。如果跑道是封闭的环那么快的人总会在某一圈追上慢的人如果跑道是直的、有尽头的快的人只会先到达终点两人永远不会相遇。所以只要快指针在移动过程中和慢指针指向了同一个节点就说明链表里有环。快慢指针还有很多变体。比如找链表的中间节点快指针每次走两步慢指针每次走一步快指针走到末尾时慢指针正好走到中间。再比如有序数组去重快指针负责在前面探路遇到不重复的元素就把它写到慢指针指向的位置。这种情况下快慢指针更像一个“读指针”和一个“写指针”——一个负责扫描原数据一个负责记录有效结果。2.3 滑动窗口同向双指针的经典形态严格来说滑动窗口是双指针的一个分支但它太常用了值得单独说一句。它的两个指针都往同一个方向移动但是维护的区间长度是动态变化的。比如求“无重复字符的最长子串”右指针不断把新字符纳入窗口左指针在发现重复字符时收缩窗口。整个过程里右指针控制“扩张”左指针控制“收缩”两者一起把窗口在整个字符串上“滑”过去每个字符最多进一次出一次时间复杂度O(n)。所以你在学习双指针的时候不要把它理解为一种固定的代码模板而是把它理解为一种区间维护的策略——用两个指针相对灵活地圈定一个范围然后在这个范围上做计算。3. 经典题目拆解从“会背模板”到“会推导”这一部分我用几道题把双指针的常用场景挨个过一遍。这些题都是我反复讲过很多遍的从最简单的开始逐渐增加难度。我建议你跟着题目自己写一遍不要只是看。3.1 题目一移动零左右指针入门题目给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。要求原地操作不复制数组。解法思路这个题用快慢指针这里更像是一个“读写指针”就能优雅解决。我们可以维护两个指针一个dest指向“已处理区间中最后一个非零元素的下一个位置”一个cur负责遍历整个数组。cur每遇到一个非零元素就把它写到dest指向的位置然后dest往后挪一位。等cur遍历完整个数组[0, dest)区间存放的就是所有非零元素的相对顺序排列剩下的位置直接补0即可。class Solution { public: void moveZeroes(vectorint nums) { int dest 0; int n nums.size(); for (int cur 0; cur n; cur) { if (nums[cur] ! 0) { nums[dest] nums[cur]; } } for (int i dest; i n; i) { nums[i] 0; } } };注意看这里我们用cur做读指针dest做写指针。cur扫描到的非零元素被搬运到前面覆盖掉那些已经没用的位置。这个思路不需要复杂的交换逻辑代码非常简洁。时间复杂度O(n)空间复杂度O(1)。这道题的价值不在于难而在于让你熟悉“读写指针”这个模式。后面很多原地修改数组的题都是这个思路的微调。3.2 题目二复写零快慢指针进阶题目给定一个固定长度的数组arr将数组中的每个0复写一遍将其余元素向右平移。注意不要超出数组长度。要求原地操作。这个题比移动零上了一个台阶。如果从前往后扫遇到0就在前面插入一个0后面的所有元素都要整体往后挪时间复杂度直接炸到O(n²)。现场写代码很容易想到这一步然后卡住不知道怎么优化。正确解法分两步第一步先找到“最后一个会被保留的元素”。这个怎么找呢用一个哨兵指针cur遍历原数组同时用一个dest指针记录“如果复写0最终会被占到的位置”。遍历过程中如果arr[cur]是0dest就加2否则加1。当dest n - 1时停止遍历。此时cur指向的就是最后被保留的元素位置。这里有个容易翻车的边界如果最后恰好是0复写完越界——比如数组长度是5最后一个有效元素是0复写时会占用第6个位置超出了数组长度。这种情况需要特殊处理直接把数组最后一个位置写成0然后cur回退一位dest回退两位。第二步从cur位置开始从后往前填写数组。为什么要逆序因为从前往后会覆盖掉还没读到的元素。逆序复制时如果当前元素是0就连续写两个0否则只写一个原值。这个逆序过程有点像一个反向的快慢指针非常巧妙。class Solution { public: void duplicateZeros(vectorint arr) { int n arr.size(); int cur 0, dest -1; // 找最后一个保留元素 while (cur n) { if (arr[cur] 0) dest 2; else dest 1; if (dest n - 1) break; cur; } // 处理边界最后一个元素是0复写完越界 if (dest n) { arr[n - 1] 0; dest n - 2; cur--; } // 逆序填充 while (cur 0) { if (arr[cur] ! 0) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } };这个题的难点在于你不仅要找到双指针的移动方式还要处理逆序复制中的边界条件。我的经验是处理这类边界时用具体的例子在纸上走一遍比如[1, 0, 2, 3, 0, 4, 5, 0]模拟到最后越界的情况你就明白为什么要加那个if (dest n)的特殊判断了。3.3 题目三快乐数快慢指针判断循环题目对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为1或者无限循环但始终变不到1。判断这个数是不是快乐数。这个题和链表有环的判断逻辑一模一样。你仔细品数位平方和的过程本质上就是一个状态转移函数。从n出发不断计算“下一个数”如果某个时刻到了1就说明是快乐数如果永远到不了1那就一定进入了某个循环。怎么高效地判断是否进入循环不用额外开哈希表记录出现过的数直接用快慢指针。慢指针每次算一步快指针每次算两步。如果存在循环快指针一定会在某个时刻追上慢指针如果不存在循环到达了1快指针会先变为1然后一直停留在1。当快慢指针相遇时如果相遇点的值是1则说明是快乐数否则就说明进入了循环。class Solution { public: int bitSum(int n) { int sum 0; while (n) { int t n % 10; sum t * t; n / 10; } return sum; } bool isHappy(int n) { int slow n, fast bitSum(n); while (slow ! fast) { slow bitSum(slow); fast bitSum(bitSum(fast)); } return slow 1; } };你可能会想这不就是链表判环吗为啥套到数字上也能用因为状态转移图本质上就是一个隐式链表——每个状态指向唯一的下一个状态。快乐数的状态空间虽然不像链表那样显式存在但逻辑结构完全一样。这就是算法的奇妙之处把不同领域的题抽象成同一个模型。3.4 题目四盛最多水的容器对撞指针经典题目给定一个长度为n的整数数组height数组中的每个元素代表一个垂直线的高度。找出其中的两条线使它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。这个题暴力做法是枚举所有下标对计算面积取最大。但细心观察会发现面积 高度较小的那条边 * 宽度所以面积由短板决定。用对撞指针初始时左指针指向最左端右指针指向最右端此时宽度最大。计算出当前面积并更新答案。然后移动较短的那条边向内移动因为如果移动较长的那条边宽度变小了但是容器的高度和原来一样面积只会更小而移动较短的那条边虽然宽度变小但有可能遇到更高的柱子使高度变大面积才有机会变大。class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ans 0; while (left right) { int v (right - left) * min(height[left], height[right]); ans max(ans, v); if (height[left] height[right]) left; else right--; } return ans; } };这个算法的正确性本质上依赖一个很朴素的观察容器的最大容量不会超过那个“狭小的短板”所限制的范围。在移动指针的过程中我们其实是在做一件事枚举所有可能的“最优解候选”——那些可能成为短板的柱子。其余的柱子组合不需要考虑因为它们的高度受限于短板无论如何不会超过已经计算过的某个面积。很多人在面试的时候能背出“移动短的那条边”这个结论但被问到“为什么移动长的边就不行”时就卡壳了。这个题你一定要把推导过程想清楚不要只背结论。3.5 题目五有效三角形的个数排序 对撞指针题目给定一个包含非负整数的数组nums返回其中可以组成三角形三条边的三元组个数。组成三角形的条件是任意两边之和大于第三边。如果我们对数组排序然后固定最大的那条边那么只需要在剩下的数中找两个数使它们的和大于这个最大边即可。具体做法先排序。然后从数组末尾开始固定最大边用双指针在[0, i-1]区间内找两个数。左指针指向0右指针指向i-1。如果nums[left] nums[right] nums[i]说明left到right-1之间所有数跟right组合都能与nums[i]构成三角形因为排序后nums[left]是最小值它加起来都能满足条件更大的数也一定能满足。此时答案增加right - left个组合然后右指针左移一位继续比较。如果nums[left] nums[right] nums[i]说明左边的数太小了怎么搭配都不够所以左指针右移一位尝试更大一点的数。class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(); if (n 3) return 0; sort(nums.begin(), nums.end()); int ans 0; for (int i n - 1; i 2; i--) { int left 0, right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { ans right - left; right--; } else { left; } } } return ans; } };这个题里i从大到小的外循环加上内部的双指针总时间复杂度是O(n²)。你会看到双指针在这里真正发挥了“批量判断”的作用——它把内层的找数过程从O(n²)降到了O(n)整个问题从O(n³)降到了O(n²)。这是双指针在大数据量场景下最有价值的地方它可以一次性排除一片连续的区间而不是一个个地判断。4. 常见问题与排查技巧实录4.1 最容易翻车的边界条件我见过太多人在双指针上栽跟头翻来翻去无非这么几个原因循环条件写错。左右指针的循环条件到底是left right还是left right核心看的是“两个指针指向同一个元素时这个元素还有没有意义”。如果题目要求找两个不同的元素那left right就够了如果允许重复使用同一个位置才用。写代码前先问自己一句指针相遇时这个元素还能不能参与计算移动指针时越界。比如你判断height[left] height[right]之后执行left一旦数组只有两个元素这个操作可能让left变成right循环条件立刻失效。所以在循环体内移动指针时要在脑中过一遍“如果这是最后一轮循环我移动完之后会不会越界”。快慢指针步数没对齐。快指针走两步时要确保fast和fast-next都不是空指针否则会解引用空指针。这个在链表中非常常见写的时候先判空再走。死循环。有时候你想移动指针但是条件不满足两个指针谁也动不了就死循环了。遇到这种情况打印每一轮的left、right和当前计算结果看看模型是不是出了问题。4.2 一个通用的调试思路纸上走一遍我强烈建议你拿到任何一道双指针题先在草稿纸上画一个数组下标图。把左指针标成L右指针标成R然后一步步模拟指针移动的过程。走完一轮你就知道这个算法是否符合预期。我知道这看起来很笨但请相信我很多看起来高深的算法题卡住的根本原因不是思路不对而是模拟过程不够细致。特别是涉及边界处理时纸上推演一遍错误就能暴露出来。比起在代码里打日志来回试这个笨办法效率反而高。4.3 识别双指针题型的思维模型速查表最后整理一个我自己总结的速查表把你常见的场景和对应的双指针类型列在一起方便你刷题时对照题目特征优先尝试的双指针类型典型复杂度有序数组找两个元素满足某种关系左右对撞指针O(n)无序数组但排序后可变成上述问题排序 左右对撞指针O(n log n)原地修改数组保持相对顺序快慢指针读写指针O(n)判断链表中是否有环/找环入口快慢指针速度差O(n)找链表中点/倒数第K个节点快慢指针拉开距离O(n)连续子数组/子串有窗口约束同向双指针滑动窗口O(n)从后往前填充数组逆序双指针/哨兵指针O(n)你把这几个场景记熟了再碰到新题时第一反应就不会是“这个是啥”而是“这题和哪个已知类型最像”。算法学习的路径本质上就是这样把陌生问题映射到你已经掌握的模型上。双指针这块内容刷题量不需要太大把上面这几道题吃透再自己找几道同类型的巩固一遍基本就稳了。我个人练下来最大的体会是双指针的高效靠的是对问题结构的洞察而不是技巧本身。你多问自己几次“为什么这道题能优化到这个程度”比多刷十道题都管用。