数组双指针全拆解：快慢、对撞、滑动窗口三道LeetCode经典题一次讲透

刷LeetCode刷到数组这一块的人大概率都绕不开“代码随想录”这个刷题路线。数组专题排在最前面不是没有道理——它本身知识点不复杂但几乎所有后续的链表、字符串、哈希表、滑动窗口、二分查找底子都在数组操作上。尤其是“数组 双指针”这个组合简直是刷题前期性价比最高的一套方法论理解成本低、代码量少、运行效率提升显著而且稍加变形就能覆盖快慢指针、左右指针、滑动窗口三大类高频题型。这篇文章就把数组01专题里的双指针问题一次性拆透。先讲双指针在数组题里的底层逻辑再用三道LeetCode经典题——移除元素、有序数组的平方、长度最小的子数组——完整走一遍实操流程最后把大家最容易踩的边界条件坑、超时坑、返回值坑集中列出来。无论你是刚开始刷数组题的新手还是已经刷了一半但总觉得“暴力解也能过、双指针就是别扭”的选手这篇文章都值得静下心看完。1. 双指针为什么是数组题的核心考点1.1 数组操作的本质随机访问快搬移成本高数组是一段连续的内存空间读任何一个位置都是O(1)的时间。听起来已经很快了但换个角度来看数组最大的弱点是“插入”和“删除”代价很高要在中间删一个元素你没法像链表那样改指针就完事必须把后面的元素一个个往前挪时间复杂度O(n)。LeetCode上很多数组题核心矛盾就在这——题目要你“原地删除某个值”或者“原地调整顺序”你每删一个元素就要搬一次数据。暴力解法写起来非常自然外层遍历找到了就内层循环把后面的元素整体前移。但这样一算最坏情况是O(n^2)数据量一大就直接超时。双指针解决的问题从本质上看正是“用一次线性遍历代替嵌套循环里的重复扫描”。它利用了数组随机访问的优势用一个指针负责“读”遍历整个数组另一个指针负责“写”维护新数组的有效位置把原来“删哪个、挪哪些”的复杂操作压缩成“一路读、有条件地写”的简单逻辑。1.2 三种双指针模式先分清再动手数组双指针看起来都差不多但实际有三条完全不同的路线。很多人在刷题时觉得“双指针我会但看到题目不知道用哪个”就是没先做这层分类。第一种是快慢指针也叫同向双指针。两个指针从同一端出发一个走得快一个走得慢。典型应用是“原地删除元素”“去除有序数组重复项”。快指针负责探索数组慢指针负责记录有效输出位置。第二种是左右对撞指针两个指针分别从数组两端出发向中间靠拢。典型应用是“有序数组的平方排序”“两数之和”“反转数组”。它能够利用数组的某种有序性每走一步就排除掉一半可能效率极高。第三种是滑动窗口本质也是同向双指针但强调的是左右指针共同“夹”出一个区间窗口通过右指针扩张、左指针收缩动态寻找满足条件的子区间。典型应用是“长度最小的子数组”“无重复字符的最长子串”。为了便于快速对照我做一个表模式指针方向典型场景时间复杂度代表题目快慢指针同向一快一慢原地删除、去重O(n)移除元素、删除有序数组重复项左右对撞相向两端向中有序数组、回文、反转O(n)有序数组的平方、反转字符串滑动窗口同向区间伸缩子数组、子串最值O(n)长度最小的子数组、无重复字符的最长子串判断一道题该用哪种我的经验是看三件事第一题目是否要求“原地操作”第二数组本身是否有序或者处理后是否有某种顺序可以利用第三要找的结果是不是一个“连续子区间”。把这三点对号入座基本就不会选错方向。1.3 不要迷信模板先理解“不变量”网上双指针的模板很多但直接背模板有一个隐患你很容易在边界条件上翻车。比如同样是fast和slow两个指针为什么有些题写while (fast nums.length)有些题却写while (slow fast)这取决于你定义的循环不变量是什么。所谓循环不变量就是循环过程中始终保持不变的逻辑规则。你在每个循环步骤开始前定义一个状态然后保证循环体执行完毕后这个状态依然成立循环结束时答案自然也就正确了。写双指针代码前先把“slow指向什么、fast指向什么、区间是左闭右开还是左闭右闭”这三句话写清楚代码只是把这三句话翻译成语法而已。我刷题时踩过最深的坑就是没想清楚区间开闭直接套模板。明明题目过了换一组测试用例就溢出或者漏元素。所以下面每一道题我都会先把“我定义的不变量是什么”讲清楚再给代码。2. 三道经典LeetCode题目实操拆解2.1 移除元素快慢指针的入门第一课题目是LeetCode 27题给你一个数组nums和一个值val要求原地移除所有数值等于val的元素返回移除后数组的新长度。不需要考虑超出新长度后面的元素是什么。这道题最直观的暴力解法是外层循环遍历数组遇到等于val的元素就内层循环把这个位置后面的所有元素整体前移一位。如果数组里有很多个val每删一个就要搬一次最坏情况下时间复杂度是O(n^2)。“能过”和“高效”的区别就在这里。快慢指针解法就优雅得多。定义一个slow指针它的含义是“下一个需要写入有效元素的位置”再定义一个fast指针负责从头到尾遍历原数组中的每一个元素。fast每遇到一个不等于val的元素就把它写到slow指向的位置然后slow向前走一步fast遇到等于val的元素直接跳过什么都不做。代码写出来是这样def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow整个过程只有一个for循环时间复杂度O(n)空间复杂度O(1)完美满足原地操作的要求。为什么这里不能用左右对撞指针因为题目要求“移除等于val的元素保持其余元素的相对顺序不变”。对撞指针对元素顺序的扰动很大比如把后面的元素往前填顺序就乱了。而快慢指针是严格按原顺序扫描的后面写入的每一个元素都来自前面扫描过的合法元素相对顺序天然不变。这就是选择快慢指针的根本原因不是谁更简单是题目要求决定了思路。实操时我一般会手工跑一遍例子来验证不变量。比如nums [3, 2, 2, 3], val 3初始slow0, fast读nums[0]3等于val跳过。fast读nums[1]2不等于val写入nums[0]2slow变1。fast读nums[2]2不等于val写入nums[1]2slow变2。fast读nums[3]3等于val跳过。结束slow2新数组前两位是[2,2]返回2。这里有个容易被忽略的细节赋值操作用的是nums[slow] nums[fast]不是交换。如果写成交换数组里val的值虽然会被推到后面但“移除后新长度后面元素无所谓”这个条件虽然允许这样但当fast和slow指向同一个元素时交换没事一旦指向不同元素写错位置就会把还没扫描的元素提前覆盖掉而且后续逻辑也会乱。这道题用覆盖就对了没必要交换。2.2 有序数组的平方左右对撞指针的典型应用题目是LeetCode 977题给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。最暴力的方法把每个元素平方然后排序时间复杂度O(n log n)。能过测试但这道题的存在意义就在于检验你是否能利用“原数组已经有序”这个信息把复杂度降到O(n)。很多人第一反应是数组有序平方之后负数变正数顺序可能就乱了该怎么办这里的关键洞察是平方后的最大值一定出现在数组的两端。因为一个有序数组里越靠左的负数绝对值可能越大越靠右的正数绝对值也可能更大所以整个平方数组的最大值只会来自最左边或最右边。于是左右对撞指针的思路就很自然了让left指向最左边right指向最右边比较两个指针对应元素的平方大小把更大的那个从结果数组的末尾往前填。填一个就移动对应的指针继续比较下一对。def sortedSquares(nums): n len(nums) result [0] * n left, right 0, n - 1 pos n - 1 while left right: left_sq nums[left] ** 2 right_sq nums[right] ** 2 if left_sq right_sq: result[pos] left_sq left 1 else: result[pos] right_sq right - 1 pos - 1 return result为什么结果数组要“从后往前填”因为每次比较选出来的都是当前剩余元素中平方最大的那个如果从前往后填先填入的是最大值最终结果会是降序的还得再反转一次。从后往前填直接得到升序结果一步到位。这里还有一个容易犯浑的细节while left right还是while left right。如果数组只有一个元素left right用left right会漏掉这个元素result最后一个位置永远空着不为0初始化值。这道题因为用pos记录填充位置当left right时这个元素是剩余最后一个必须填进去所以必须用。这正好呼应前面说的“循环不变量”——你要保证每一个原始元素都被考虑过一个都不能少。不用调排序接口也不引入额外数组来暂存空间复杂度O(1)就完成了排序效果这就是双指针的魅力。2.3 长度最小的子数组滑动窗口的收缩逻辑题目是LeetCode 209题给定一个含有n个正整数的数组和一个正整数target找出该数组中满足其和大于等于target的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回0。暴力解法很好想枚举每一个起点然后向后累加直到和大于等于target就记录长度。两层循环最坏O(n^2)。问题出在哪呢每一轮内层循环都在重复累加之前已经加过的元素这部分计算是冗余的。滑动窗口的思路是把“起点固定、终点移动”改成“窗口整体滑动”。用right指针不断向右扩张窗口同时维护一个window_sum记录窗口内元素的和。每次right前进一步就把新元素加入window_sum。一旦window_sum大于等于target说明当前窗口满足条件了记录长度。然后想办法缩小窗口——怎么缩让left指针向右移动每移一位就从window_sum里减掉对应元素再检查一次是否依然满足如果满足就继续缩。直到不满足了再让right继续向右扩。def minSubArrayLen(target, nums): left 0 window_sum 0 min_len float(inf) for right in range(len(nums)): window_sum nums[right] while window_sum target: min_len min(min_len, right - left 1) window_sum - nums[left] left 1 return 0 if min_len float(inf) else min_len这段代码有一个很关键的思维转变while循环收缩左边界实际上就是在枚举所有可能的子数组终点同时以最经济的方式枚举起点。暴力解法的冗余在于固定一个起点后要一直加到很远才知道结果而滑动窗口一旦发现当前窗口满足条件立刻收缩左边界尽力寻找更短的窗口不满足条件后再向右扩展。这样left和right各自最多遍历数组一次总复杂度是O(n)。我在实际讲这道题的时候常用一个类比好比手里拿一把卷尺右端先往外拉拉到长度够了左端就往回收看能不能更短左端收到不够长了右端再继续拉。整个过程卷尺一直没离开过测量范围这就是滑动窗口的直观画面。有一点必须提醒这题能用滑动窗口的前提从题目描述就能看出来——数组是正整数。如果数组有负数窗口变长的同时sum不一定是单调增加的收缩逻辑就不成立了。所以刷题遇滑动窗口先确认数组元素的非负性这是一个极其重要的前置条件。3. 边界条件与易错点排查3.1 数组越界的几种死法刷数组题越界是所有错误的根源之一。双指针尤其容易在循环条件和指针自增顺序上出错。最常见的三种死法我都踩过。第一种fast指针越界。快慢指针遍历时习惯性写成while (fast nums.length - 1)本来没错但如果你在循环体里写了nums[fast 1]当fast指向最后一个元素时就会越界。解决方法是如果明确只需要访问当前fast位置写成while (fast nums.length)即可要访问fast 1位置的话得把循环条件写成while (fast 1 nums.length)思路完全不同。第二种left指针越过right指针后还在交换。对撞指针的标准写法是while (left right)但如果你在循环体里先移动left再判断就可能在left right之后又执行了一次赋值操作把已经处理过的区域重新覆盖。我的习惯是所有指针更新都放在循环体最后并且每更新完一个指针就重新检查一次边界不要等到下一轮循环再检查。第三种滑动窗口right跑到尽头后left还在继续右移。注意上面209题的 while 循环是嵌套在 for 内部的for right in range(len(nums))结束后外层循环就终止了。如果在同一个循环里又对left做了其它操作或者想继续收缩窗口找更短答案一定要先封装好递归或者继续单独一个while避免凭空访问不存在的元素。3.2 循环不变量先写清楚再用代码翻译我在前面反复强调“循环不变量”这个词是因为它是双指针调试的核心工具。数组题不像设计模式它没有太多“封装”的余地所有逻辑就是指针的移动和数组元素的读写。如果循环不变量不清晰代码是写不对的。拿移除元素举例我的不变量定义是nums[0...slow)这个左闭右开区间内存放的是所有已扫描过的、不等于val的元素而这个区间的长度正好是slow本身。基于这个不变量结尾直接return slow就是合法长度根本不需要再数一遍元素个数。拿有序数组的平方举例不变量是result[pos1...n-1]已经存放了平方值最大的若干个元素且排列是递增的。每次比较两端平方后填入result[pos]这个不变量就一直保持最后整个result有序。在纸上写下这行定义通常只需要一分钟。但这一分钟能避免你在写错条件后在debug里浪费一个小时。我们刷题追求的不是“跑过了就算”而是“每一步都有逻辑依据”。3.3 调试与边界用例设计写完整段代码不要直接提交。先自己构造几个极端用例跑一遍这几类用例我屡试不爽空数组[]候补答案是0还是-1接口返回值是否符合预期。单元素数组[5]val正好等于5或者不等于5。全相同数组[2,2,2]val2快慢指针的slow全程不动看会不会越界。目标值恰好等于边界值比如target6数组[2, 3, 1, 2]只有整个数组加起来才刚好等于6或者差一点点。数组元素全为负数或全为正数验证对撞指针的平方排序是否依然成立。我有一个超实用的调试技巧在循环里加一行临时打印把slow和fast或left和right以及当前数组状态输出出来。跑两三轮马上就能看出指针是不是按照预期在移动。很多代码看起来“逻辑没问题”一跑起来才发现指针顺序反了、先写后读搞反了。打印就是最快的定位方式。4. 常见问题排查与刷题节奏建议4.1 常见问题速查表把双指针数组题最常遇到的报错和维护问题整理成一个表方便遇到问题直接对号入座现象可能原因排查思路运行超时TLE仍在使用嵌套循环每次滑动窗口重新求和检查是否存在O(n^2)代码维护窗口累加值数组下标越界IndexOutOfBounds循环条件写错fast访问了fast1left超过right后继续操作统一用而非所有指针移动放循环尾先判定边界再读写返回结果长度不对忘记slow本身就是新长度或误用了原数组长度确认返回值是slow、left等指针的最终位置结果顺序不对对撞指针从前往后填区间开闭定义不一致明确升序/降序要求必要时从结果数组尾部倒序填入某些测试用例通过某些失败循环内提前返回边界判断与主体逻辑混在一起单独设计空数组、单元素数组等极端用例逐一调试4.2 为什么推荐按照代码随想录数组专题的顺序刷代码随想录把数组01放在最前面接着就是二分查找、移除元素、有序数组的平方、长度最小的子数组这个顺序不是随便排的。它是在用几个最典型的题目把数组题最核心的四种操作——查找、删除、排序、子区间——都覆盖一遍。而双指针恰好是这四类操作里最有复用价值的工具。我建议第一遍刷的时候每道题都按“暴力解法 - 双指针解法 - 总结不变量”三部曲来走。不要一上来就想着最优解暴力代码虽然效率低但它能帮你理清问题本身到底在要求什么。然后在此基础上推导为什么可以省掉一层循环其实就是在逐步接近双指针的设计思路。第二遍刷的时候尝试“裸写”——不翻笔记不看题解直接写代码。你会发现第一遍理解的“不变量”在裸写时会暴露大量漏洞因为参考答案时你只是看懂自己写时需要真正组织逻辑。第三遍隔一周再回来写重点写变体题。比如移除元素改一个条件变成“删除所有重复项”“移动零到数组末尾”滑动窗口改一个维护指标变成“乘积小于k的子数组”。这种变体训练比做十道新题还有用。4.3 双指针学到什么程度算“入门了”我的判断标准很简单。第一看到一道数组题能快速说出它属于快慢、对撞、滑动窗口中的哪一类或者能明确说出为什么不属于任何一类第二能写出循环不变量哪怕不写在纸上心里要有一句清晰的话第三能在不查资料的情况下写出O(n)的解法并且能对着极端用例解释代码为什么不会越界。这三点都做到了数组01专题就可以算过。之后遇到的链表双指针环形链表判断、寻找倒数第k个节点、字符串双指针反转字符串、验证回文串、哈希表与双指针的组合题三数之和、四数之和其实都是今天这三道题的变形。底子打牢了后面的路会顺畅很多。最后分享一个我个人的习惯每次做完一道双指针题我都会在代码注释里写一行“这里如果改成XX条件就会用到另一种指针模式”算是给自己留一条思考的记录。三个月后回头看你会发现当初在评论区、题解里死记硬背的东西突然都能串起来了。数组双指针是算法面试前几关中最值得反复打磨的一关练熟它性价比极高。