双指针精讲：从移动零到数组原地压缩的通用套路

LeetCode hot100 里的移动零我隔一阵子就会刷到一次每次看都觉得这题简直是把“双指针”三个字浓缩成了一碗汤。题面很朴素给定一个数组把所有0移动到末尾同时保持非零元素的相对顺序并且不能拷贝额外数组。很多第一次刷到它的人会觉得这有什么好讲的但就是这道题让我把数组类题目里最核心的“快慢指针”思想彻底吃透了后来做移除元素、去重、奇偶分区全都靠着同一个套路。这篇文章会从暴力解讲起一步步把双指针解法推出来再把我实际刷题踩过的坑、以及怎么把这道题的思路迁移到同类型题目上全部展开说清楚。如果你刚上路想找一道能练手又能举一反三的题移动零是比较理想的切入口。1. 先读懂题面移动零到底在考什么1.1 题面里的两个硬约束先把题目里的信息拆开看。数组 nums 里混着若干个0和非零整数要求把所有0挪到数组末尾剩下的非零元素保持原来的相对顺序。这里有两层约束第一层是“保持相对顺序”第二层是“必须原地操作不能拷贝额外的数组”。第一层约束在暗示什么它直接排除了“随便交换”的念头。比如你把数组 [0, 1, 0, 3, 12] 随意重排成 [1, 3, 12, 0, 0] 行不行行但你要是把一个非零元素挪到另一个非零元素前面去顺序就乱了。就比如从后往前交换很容易让原本在后面的非零元素跑到前面来最终结果虽然0都在后面但非零顺序被打乱直接判定错误。这层约束其实是在提醒你这道题要的不是“归位”而是“有序压缩”。第二层约束是在考验你是否理解什么叫真正的原地算法。有些人的第一反应是新建一个数组非零按序填进去再补0复制回原数组。这确实能过测试用例但不符合“不能拷贝额外的数组”的要求。面试场景里你一旦写出这种方案面试官就开始追问“能不能原地做”追着追着很多人就慌了。所以与其在开新数组的方向上浪费时间不如一开始就盯准原地操作。1.2 什么解法从一开始就可以排除做题最忌讳一上来就默写答案而是要先把明显不靠谱的路子划掉。第一种是嵌套循环交换法外层遍历找0内层往后再找到一个非零然后两者交换位置。逻辑上没错但复杂度和边界都很糟最坏情况是数组形如 [0, 0, 0, 0, 1]每个0都要扫描到数组最后才发现一个非零整体时间复杂度接近 O(n²)在数据量大时必然超时。第二种是开新数组再拷贝虽然时间复杂度是 O(n)但额外空间是 O(n)直接被题面里的“不能拷贝额外数组”否掉。第三种是排序思路比如用稳定排序把0沉底理论可行但排序的 O(n log n) 复杂度对这道题来说完全是多余操作。把这些方案全部排除之后你会发现留给你的选择空间其实已经指向双指针了。这就是分析题目的价值你不但知道正确答案是什么也知道正确答案为什么一定是它。2. 从暴力解到双指针思路是怎么一步步逼出来的2.1 暴力解的复杂度陷阱很少有人会长期停留在这个阶段但面试时却总有人下意识地提嵌套循环方案。我想说的是如果一个算法里出现了“找0再找下一个非零”这种二元逻辑基本就要警惕起来。因为这相当于每个0都可能引发一次对后续区域的扫描而扫描本身是线性成本。多个0叠加起来就是典型的平方级成本。相较之下正确解法应该做到“每个元素只看一次”而且尽量不回头。数组题里一旦把目标定为“每个元素只看一次”你的解题武器库就只剩几个固定模型了双指针快慢指针、对撞指针、滑动窗口、前缀和。移动零没有“连续区间求和”这类需求也没有“从两端向中间逼近”的天然规律所以最合适的就是快慢指针模型。这也是为什么说“约束决定解法结构”不是我们非要选双指针而是别的方案全被约束堵死了。2.2 快慢指针的分工与设计逻辑快慢指针的核心分工是这样的fast 指针负责“读”它从数组头走到尾逐个检查当前元素是否是非零slow 指针负责“写”它始终指向“下一个非零元素应该在的位置”。凡是碰到非零就直接把它放到 slow 指向的位置然后 slow 前进一格。如果碰到0fast 继续走slow 原地不动。这里可以类比成流水线分拣传送带上送来一个个货物合格的放到打包台上打包台从出口开始依次往后摆空货位和不合格的货物根本不用处理只有合格货物经过打包台时才会被放置。slow 就是“打包台上的下一个空位”fast 就是“传送带上当前的货”。当你把这道题理解成“一边扫描、一边按顺序填放”你就会发现所有0在被 fast 跳过之后最终自然会被留在数组尾部。为什么因为所有的非零都被顺序填到前面去了剩下的槽位毫无悬念都是0。2.3 遍历方向为什么不能反着来初学者容易产生一个念头既然要“往后放0”那我从数组后面开始遍历把非零往前挪不是一样的吗我一开始也这么琢磨过后来写了代码才发现问题。从后往前扫描你在“寻找非零放到前面”的过程中很难保住非零元素的相对顺序。举个例子[1, 2, 0, 3]如果你从后往前找非零找到3放到后面某个空位时你很难确保3不要跑到2后面去。除非你再精心设计几个额外标记但这样一来代码复杂度远超正向快慢指针。所以正向遍历不是惯性选择而是由“保持相对顺序”这个要求决定的。正着扫你读元素的顺序就是最终非零元素应该出现的顺序正着填你填出来的位置也严格按这个顺序走两者天然一致。反向遍历时读的顺序是逆的你还得再反转一次徒增麻烦。这个对比让我更认同一句话代码结构本身就是约束条件的镜像。3. 核心实现与代码逐行解析3.1 最推荐的覆盖加补零版本先给最推荐的双指针写法用 Python 写非常直观def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow] nums[fast] slow 1 for i in range(slow, len(nums)): nums[i] 0第一个循环负责把所有非零数字按顺序“提取”到数组前部。第二个循环负责把从 slow 位置开始的所有元素统一赋值为0。为什么要分两个阶段因为第一阶段只处理非零处理完之后数组的尾部还残留着旧的非零值如果不把它们覆盖成0输出就是不正确的。我们用一个例子完整走一遍过程。假设 nums [0, 1, 0, 3, 12]。初始 slow 0。fast0 时nums[0]0跳过。fast1 时nums[1]1执行 nums[0]1slow 变1数组变成 [1, 1, 0, 3, 12]。fast2 时nums[2]0跳过。fast3 时nums[3]3执行 nums[1]3slow 变2数组变成 [1, 3, 0, 3, 12]。fast4 时nums[4]12执行 nums[2]12slow 变3数组变成 [1, 3, 12, 3, 12]。第一阶段结束slow3。第二阶段从下标3开始到末尾全部赋0得到 [1, 3, 12, 0, 0]。这个例子你可能已经看过很多遍但我建议你亲手在草稿纸上画一遍。尤其是要留意 slow 的变化节奏每放一个非零它只前进一格而不是按照 fast 的节奏走。把自己代入这个变量很多边界理解上的模糊感会一下消失。3.2 交换双指针写法与对比另一种常见写法是交换法每遇到非零就把它和 slow 位置交换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往后带。它和覆盖法的关系有点像“搬东西”和“填坑”覆盖法是先把好东西搬到新位置最后还记得把老坑填平交换法是搬东西的同时顺手把垃圾扫到后面不需要单独的清理阶段。在数组几乎全是非零的场景下比如 [1, 2, 3, 4, 5]交换法会出现大量“自己和自己交换”的无意义操作。覆盖法在这一场景也没好到哪去它执行的是“自己给自己赋值”。这两种情况对现代计算机来说都算不上什么性能负担但如果在追求极致效率的场合可以在代码里加一个判断如果 fast ! slow 才执行移动或交换。这样可以把无意义操作直接跳过。另外要提一个对比点覆盖法在阶段结束后数组尾部会残留旧值必须依靠补零来清理交换法则没有残值问题但交换过程可能多出额外开销。两者都是 O(n) 时间和 O(1) 空间选哪个主要看你更在意“代码简洁”还是“避免多余操作”。我面试时通常会先写覆盖法因为它的思考步骤更线性逻辑漏洞更少。3.3 复杂度证明与判例分析时间复杂度的计算非常简单第一遍循环最多执行 n 次第二遍循环最多执行 n 次两者是先后关系而非嵌套关系所以总时间复杂度是 O(n)。空间上只引入了一个 slow 变量没有额外数组所以是 O(1)。我们可以验证几个极端输入。全0数组 [0, 0, 0, 0]第一遍 fast 每次路过都跳过slow 一直为0第二遍从下标0到3全部赋0。总执行步数约 2n。全非零数组 [1, 2, 3, 4, 5]第一遍每个元素都把自己赋值到自己所在位置slow 走到 n第二遍循环范围为空不执行。总执行步数约 n。最坏情况仍然是线性增长不会因为输入分布不同而退化成平方级。这里有必要给新手一个提醒两个 for 循环不是嵌套不要看到多个 for 就觉得复杂度要相乘。只有当一个循环完整执行时另一个循环又在内部从头执行才构成乘法关系。移动零的两个循环是“先做完第一步再做第二步”的流水逻辑复杂度是加法关系。搞懂这一点你后面看很多双指针题都会舒服得多。注意补零的范围是range(slow, len(nums))不是range(slow 1, len(nums))。slow 指向的是“第一个应该变成0的位置”而不是“第一个不用处理的位置”多写一个 1 就会漏掉下标 slow 处的旧值。4. 我实际写这题踩过的坑问题排查实录4.1 补零范围写错我第一次写覆盖法时就是栽在补零范围上。当时脑子里的逻辑是slow 已经指向下一个写入位置所以从 slow 开始补零但又觉得 slow 这个位置好像“刚刚被写过”不自觉就写成了 slow1。结果数组尾部残留了一个非零值测试用例没过。定位这个 bug 的方法很简单先拿一个短数组比如 [0, 1, 0, 3, 12]手动跑完第一阶段后打印数组看一眼哪里不对。我后来总结出一个固定检查点在第一阶段结束后直接打印 slow 和 nums你就能瞬间判断问题出在“覆盖阶段”还是“补零阶段”。这个调试习惯帮我省了很多时间也推荐给你。4.2 把覆盖法和交换法的收尾工作搞混有一次我写代码时内心想的是覆盖法结果写了一半脑子里又闪现交换法“不用补零”的优点于是漏掉了补零循环。提交后发现数组后面全是原来的非零值才意识到自己把两种解法的收尾逻辑混在一起了。这个教训让我养成了一个习惯写代码前先决定用哪一种语义并且在注释里明确标出来。用覆盖法就在开头写上“覆盖后必须补零”用交换法就写“交换天然处理好0无需补零”。代码注释不光是给别人看的更是防止自己思维漂移的锚点。4.3 忍不住想开额外数组这是我见过最多的新手错误。虽然题面写了“不能拷贝额外数组”但总有人写出类似下面这种逻辑先统计非零个数再声明一个新列表把非零都放进去最后在原数组里切片替换。这种写法测试能过但从题目训练的角度讲毫无意义。LeetCode 的判题系统不会因为你用了额外数组就报错但它在真实面试里是一个高危动作面试官下一句话大概率就是“能不能不额外开空间”。所以练习时建议主动给自己加一道检查任何数组题如果题面提到“原地”我就默认不允许申请和原数组规模相关的额外空间。这是一种思维训练能让你在真正面试时条件反射地避免这类方案。4.4 交换法里遇到换过来的0要不要回头处理使用交换法时有个很容易迷惑的操作执行nums[slow], nums[fast] nums[fast], nums[slow]之后下标 fast 位置上往往变成了一个0。不少新手看到这个0就会想“这不是一个0吗fast 不应该在这里继续处理吗”这是对快慢指针职责的误解。fast 的位置是“扫描读取元素的位置”它刚才要处理的元素已经处理完了换过来的0是“留下的旧值”不需要再检查。慢指针 slow 是“写入位置”它关心的也不是 fast 处的值而是找到下一个非零。早年间我在这里卡了很久后来用一句“每个元素最多被处理一次”来提醒自己就不会再纠结了。数组双指针题有一个共同的防错心法时刻问自己fast 的职责是“读”slow 的职责是“写”两者职责分离边界就清晰了。5. 一道题吃透一类题快慢指针思路的可迁移性5.1 移除指定值条件替换LeetCode 27 题“移除元素”和移动零几乎同构。题面要求是给定数组和一个值 val原地移除所有数值等于 val 的元素返回新长度。把移动零代码改一下判断条件从nums[fast] ! 0改成nums[fast] ! val然后把补零阶段删掉因为新长度之后的元素不需要关心。这个变形让我第一次意识到“移动零”是一个更一般的“按条件压缩数组”问题的特例。把条件换成“等于某个值”或“不等于某个值”模板不变问题就能通吃。5.2 有序数组去重判断条件改变LeetCode 26 题“删除有序数组中的重复项”同样是快慢指针模板。这题的 fast 扫描每个元素slow 指向最后一个已保留的元素。当nums[fast] ! nums[slow]时说明遇到了新的不同元素把它放到 slow1 的位置并让 slow 自增。这个判断条件从“不等于0”变成了“不等于上一个保留元素”但整体结构依然是一遍扫描、一遍写入。我能给出的迁移经验是遇到新的数组题先问自己“我需要保留哪些元素保留顺序是什么”然后把“保留条件”写成一个布尔表达式。只要这个表达式能对每个元素独立判断快慢指针大概率就是最合适的解法。移动零、移除元素、去重全都符合这个特征。5.3 奇偶分区与更一般的分区操作数组里把奇数放前面、偶数放后面或者把负数放左边、非负数放右边同样可以用快慢指针。区别在于快慢指针方案会保持其中一部分的相对顺序。如果题目不要求顺序你甚至可以改用对撞指针从两端同时扫描交换效率有时更直观。但如果要求顺序快慢指针仍然是稳妥的选择。这种“分区思想”在后续刷题里还会反复出现比如荷兰国旗问题、三路快排的思想源头都能追溯到“在一个数组里按照规则切分区域”。移动零正是最简单的一种“切分”慢指针把数组切成了“已处理区”和“未处理区”。我后来看很多复杂的排序算法都会想到这道题因为排序本质上就是按照某种规则对数组做分区只不过规则更加复杂而已。5.4 微观优化如何减少无意义赋值面试中如果已经写出了标准解法面试官可能会追问“能不能再优化一点操作次数”。这时可以给出一个演进版本只有当 fast 和 slow 不相等时才执行移动否则说明当前元素本来就在正确位置直接 slow 即可。def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: if fast ! slow: nums[slow] nums[fast] nums[fast] 0 slow 1这个版本的特点是对于本来就排好的数组比如 [1, 2, 3, 4, 5]它完全不会发生“自己赋值给自己”的冗余操作。对于包含0的数组它也能减少一部分赋值。虽然 LeetCode 判题上这不会带来数量级的差异但能展示你对“操作次数”的理解。这道题的题面里有一句“尽量减少操作次数”很多人忽略了它其实这就是在暗示你可以往这个方向优化。顺带一提这句“尽量减少操作次数”在工程上对应的是“减少不必要的内存写操作”。内存写操作在某些场景下比读操作昂贵许多尤其是数组大到超出缓存时。能减少写就能减少实际耗时。你在面试里如果能说出这句话会显得非常有工程意识。6. 面试怎么答、工程怎么用双指针题的正确打开方式6.1 思路表达顺序决定面试观感如果面试官让你现场写这道题我建议不要直接开始敲代码。先花二十秒把思路讲清楚先提到“新建数组被禁止”再说“嵌套交换会超时”然后引出“快慢指针”的核心——fast 负责扫描找非零slow 负责标记写入位置最后补上一句“时间复杂度 O(n)空间复杂度 O(1)”。这个顺序能充分展示你分析问题、排除干扰方案、然后落到最优解的过程。面试官最怕的不是你写得慢而是你默写模板却讲不出为什么。这道题恰恰是展示“为什么”成本最低的一道题。6.2 原地操作在工程中的真实价值从工程角度看原地操作不是花架子。数组在内存里是连续空间原地移动元素能更好地利用 CPU 缓存。如果你频繁创建新数组再把数据复制来复制去不仅额外分配内存还可能导致读写跨度大、缓存命中率降低。在业务代码里偶遇“需要过滤一批无效数据但又要保留原数组供后续复用”的场景并不少见。比如一个日志数组要把某种类型的日志剔除剩下的按原顺序保留这和移动零的思路完全一致只不过把“非零”换成了“满足保留条件”。这几年我写数据清洗类代码时越来越习惯用这种“原地压缩”的套路避免为了过滤一个字段就复制出若干个数组内存占用会更可控。这道题虽然小但它教给你的“原地数组压缩”模式在工程实践里是有真实价值的。6.3 “逐元素交换”与“定点投放”的差异如果你尝试用类似冒泡的思路把0一个一个往后交换也能解决问题但复杂度就是 O(n²)。而双指针做到 O(n) 的关键在于它不让0一个一个“漂移”而是让非零元素直接跳到它最终的落点。换句话说移动零的每一步都在做“定点投放”而不是“逐字节搬运”。这个理解非常重要因为很多题从暴力解到最优解的跃迁恰恰就是“搬运”思维升级成“投放”思维的过程。快慢指针的本质就是为每一个待处理元素找到它最终的位置并且只移动一次。这个角度也能解释为什么快慢指针在多数情况下比对撞指针更优秀对撞指针通常用于“两端逼近”的题目比如盛最多水的容器、两数之和而快慢指针用于“顺序压缩”的题目比如去重、移零、移除元素。两者没有高低之分只是适用的语义不同。把这道题做透之后你再去刷“删除有序数组中的重复项”“移除元素”几乎可以做到秒写。7. 写在最后这道小题教我的事移动零刷了很多遍之后我反而越来越觉得它是一个被低估的题。它没有复杂的数学推导也没有刁钻的数据结构却把“约束决定解法”“职责分离”“原地操作”这几个核心思维浓缩在一起。如果你只是背下代码那它只是一道微不足道的简单题如果你愿意顺着分析一遍它就是双指针体系中最称职的领路人。我个人实践中还有一个习惯遇到这类的题不管多简单都会先在纸上拿几个极端用例跑一遍全是最前面的0、全是最末尾的0、所有元素都是0、所有元素都不是0。这四个用例基本能覆盖掉九成的边界问题比反复提交等报错高效得多。移动零如此后来的二分查找、滑动窗口题也如此。最后再分享一个很小的技巧如果你用覆盖法可以在第一行注释写上“slow 下一个写入位置fast 当前扫描位置”然后写每一步代码时都对照这句注释。很多边界 bug 在你真正理解这两个指针职责之后会大幅度减少。希望你刷完这道题也能拥有这种“一眼看穿数组题”的感觉。