LeetCode 283 移动零：双指针原地算法详解与面试解析

最近在整理刷题笔记把 LeetCode 283“移动零”这道题翻出来重新过了一遍。别看难度标着 Easy双指针入门几乎都会拿它当第一道例题。题目本身一句话就能说完给定一个数组nums把所有 0 移到数组末尾同时保持非零元素的相对顺序并且要求原地修改不返回新数组。但能学到的东西却很实在——怎么用两个指针把原本要反复搬移的操作压缩成一趟扫描怎么在不开新数组的前提下完成数据清洗。准备算法面试、刚开始接触双指针、或者想巩固数组操作的朋友都可以把这篇当一份带注释的思路笔记来读。我最早刷这道题时第一反应是“遍历数组看到 0 就删掉再 append 到末尾”听起来很直白跑起来却很糟糕。后来把双指针的思路吃透才发现这道题的价值远不止“把 0 挪走”这么简单。它背后牵出的是原地算法、稳定性、不变量这三个概念而这三样东西几乎会出现在后面所有双指针题目里。这篇就把题目拆开讲从暴力解到双指针最优解从代码细节到面试追问全部过一遍。1. 这道题到底在考什么移动零的题目拆解1.1 题目本身和它真正的考点先明确题目要求给定数组nums例如[0, 1, 0, 3, 12]调用函数后要变成[1, 3, 12, 0, 0]。这里有两个硬性约束一是必须原地修改不能新建一个数组然后返回二是非零元素的相对顺序不能变1 不能在 3 后面12 不能在 3 前面只能整体前移0 统一落到末尾。很多人觉得“相对顺序不能变”是理所当然的但注意这个约束其实是整个题目最关键的设计点。如果题目允许重排那解法就完全不一样了比如可以把所有非零元素先收集起来再随便放甚至直接排序。但现实中当数组里的元素代表业务数据时顺序往往承载着语义。举个例子一组订单记录按时间排列你把有效订单挑出来放到前面如果破坏了时间顺序后续处理就全乱了。所以“稳定移动”才是这道题真正要考的。除了稳定性考点还有两个第一能否识别出数组删除操作的高昂代价第二能否想到用两个指针代替“删除追加”这种直觉解法。面试官问这道题一般不是考你会不会写而是考你能不能在写完之后清晰地讲出为什么这样写是对的、时间复杂度是多少、能不能进一步优化。1.2 边界条件真正拉开差距的地方算法题里边界条件往往比主逻辑更能反映一个人的熟练度。移动零也不例外。常见的边界用例有空数组[]、单元素数组[0]或[1]、全零数组[0, 0, 0]、无零数组[1, 2, 3]、零和非零交替出现[0, 1, 0, 2, 0]。这些用例预期输出都不难猜但处理不好就会出现索引越界、尾部残留旧值这类问题。输入预期输出说明[][]空数组直接返回不能访问任何下标[0][0]只有一个 0结果不变[1][1]只有一个非零元素结果不变[0, 0, 0][0, 0, 0]全零数组没有任何非零元素需要前移[1, 2, 3][1, 2, 3]没有 0数组保持不变[0, 1, 0, 3, 12][1, 3, 12, 0, 0]标准用例非零按原顺序前移[0, 0, 1][1, 0, 0]0 全在开头非零只有一个移到最前我在给面试者出这道题时经常会在对方写完代码后补一句“如果数组开头连续有 1000 个 0你的代码会不会反复搬移那些已经放好的元素”如果答不上来说明他对算法的复杂度分析还没形成直觉。这个问题其实就是引导对方往双指针方向走。2. 双指针的思路拆解为什么从 O(n²) 到 O(n)2.1 暴力解到底慢在哪先看很多人第一反应的写法遍历数组看到 0 就执行del nums[i]然后再nums.append(0)。这种写法在思路上没有错但它默认了一个前提数组删除元素是廉价的。实际上数组在内存里是连续存储的删除中间某个元素时后续所有元素都必须往前挪一格。假设数组有 n 个元素删除一次最坏要移动 n 个元素如果数组里有大量 0反复删除加追加总体复杂度很容易膨胀到 O(n²)。当 n 到十万级别时这种写法会明显卡顿在面试现场直接超时也不是没可能。另一种直觉解法是“用新数组收集非零元素”遍历一遍把非零拷进去然后在末尾补 0最后再复制回原数组。这个解法时间复杂度是 O(n)空间却是 O(n)不满足题目“原地”的要求。如果面试官较真复制回原数组这一步虽然能骗过编译器但本质上还是用了额外空间。暴力解法的问题在于它把“移动 0”理解成了“删除再插入”而删除和插入都是基于数组连续内存特质的重操作。真正高效的做法应该换一个角度我们根本不需要关心 0 去了哪里只需要保证非零元素按顺序占据数组前面的一段连续区间剩余位置天然就是 0。这就引出了双指针。2.2 快慢指针一个负责找一个负责放双指针解法的核心是定义两个指针各司其职。慢指针slow指向“下一个非零元素应该放置的位置”快指针fast负责扫描整个数组寻找非零元素。每次fast遇到一个非零值就把它放到slow指向的位置然后slow前移一位。如果fast遇到 0则跳过不产生任何操作。这个过程可以理解为传送带分拣fast是传送带上移动的探头slow是当前可以落货的空位。有效货物非零元素被搬到前面的空位空箱子0不需要搬到任何位置就留在原地最后自然集中在后半段。为什么有序性不会丢失因为slow的位置永远是当前已处理区域的末尾fast遇到的非零元素按扫描顺序写入先扫描到的必然先写入相对顺序自然保持不变。这里最需要记住的不是代码而是不变量在任意时刻nums[0..slow-1]这一区间内全部是非零元素且保持原数组中的相对顺序。后面写代码、查 bug、和面试官解释都靠这句话撑腰。2.3 覆盖补零和交换法选哪种更好双指针落到代码上有两种常见风格。第一种是覆盖补零法第一遍把所有非零元素覆盖到前面第二遍把slow之后的区域全部置 0。第二种是交换法遇到非零元素时和slow位置交换一趟循环完成。两种方法的时间复杂度都是 O(n)空间复杂度都是 O(1)但在操作细节上有差别。实现方式遍历次数写操作特点可读性覆盖补零两次循环非零写一次末尾补 0 一次逻辑直白更容易理解适合教学交换法一次循环每遇到非零就执行交换代码简洁面试常用但需要解释交换的合理性我个人的建议是两种都要会。先把覆盖补零法写熟练因为它最不容易出错适合在高压面试里求稳再用交换法做优化版本并准备好解释“为什么交换不会打乱非零顺序”。有不少人只背了交换法的代码被追问一句“这里为什么可以直接交换”就卡住了很可惜。3. 代码实现与关键细节可复制的两种解法3.1 覆盖补零版思路最直观的写法先看覆盖补零版的 Python 实现代码非常短def move_zeroes(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表示当前没有已放置的非零元素。fast从头扫到尾只要发现非零值就把它写到nums[slow]随后slow加一。这里用的是“覆盖”而不是“交换”所以被覆盖位置原来的值是什么不重要因为那个位置要么是 0要么是已经处理过的旧值。第一遍循环结束后slow正好等于数组中非零元素的个数从slow到数组末尾的位置全部需要补 0第二遍循环完成收尾。补零这一步很容易被漏掉。如果只做第一遍覆盖不补零输入[0, 1, 0, 3, 12]会变成[1, 3, 12, 12, 12]后两位残留了原始值结果完全错误。因为覆盖只是把非零元素往前搬并没有主动清理旧位置旧数据还留在那里。3.2 交换版一次遍历的高频面试答案交换版代码也很简洁def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[fast], nums[slow] nums[slow], nums[fast] slow 1核心逻辑是slow指向下一个非零元素该放的位置当fast遇到非零元素时直接把nums[fast]和nums[slow]交换。如果slow fast交换的是同一个元素没有任何副作用如果slow fast由于中间夹着的全是 0所以nums[slow]此时一定是 0交换后这个 0 会跑到fast的位置也就是快慢指针之间继续保持“中间全是 0”的状态。C 版本同样简洁#include vector using namespace std; void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { swap(nums[fast], nums[slow]); } } }我用一个逐步走查来演示交换法的执行过程输入[0, 1, 0, 3, 12]步骤fast 下标当前值slow操作操作后数组1000跳过[0, 1, 0, 3, 12]2110交换slow 变 1[1, 0, 0, 3, 12]3201跳过[1, 0, 0, 3, 12]4331交换slow 变 2[1, 3, 0, 0, 12]54122交换slow 变 3[1, 3, 12, 0, 0]注意第 4 步nums[slow]是nums[1]也就是 0和 3 交换后0 来到下标 3 的位置正好落在快慢指针之间。整个过程不需要额外记录“这个 0 是从哪挪过来的”因为快指针会继续往后走这个 0 不会再被碰到最终整体上被推到末尾。3.3 边界用例与自动化验证写算法题的时候我习惯在本地建一个测试函数用assert跑几组边界用例比反复在在线评测系统里提交要高效得多。下面这段测试代码可以直接复制到本地跑def test_move_zeroes(): cases [ ([0, 1, 0, 3, 12], [1, 3, 12, 0, 0]), ([0], [0]), ([], []), ([0, 0, 1], [1, 0, 0]), ([1, 2, 3], [1, 2, 3]), ([1, 0, 2], [1, 2, 0]), ([0, 1, 0, 1, 0], [1, 1, 0, 0, 0]), ] for nums, expected in cases: move_zeroes(nums) assert nums expected, fcase failed: {nums} ! {expected} print(all tests passed)跑完这组用例基本上就能覆盖绝大多数边界情况。如果还想更稳一点可以补一个随机测试生成随机数组和“保留非零元素、补零”的参考实现做对比。随机测试能发现一些手写用例想不到的问题尤其是交换法里下标错位这类隐蔽 bug。4. 常见错误、排查技巧与面试追问4.1 新手最容易踩的五个坑我在帮别人 review 这道题的代码时见过很多次相同的错误。把它们集中整理成一张表方便对照自查错误现象根本原因解决办法输出尾部残留旧值覆盖非零后忘记补 0第一遍循环结束后必须把slow到末尾全部置 0非零元素顺序被打乱slow每次循环都自增而不是遇到非零才自增slow 1必须放在if nums[fast] ! 0分支里数组变成全 0判断条件写反处理了nums[fast] 0的情况改成判断非零即! 0遍历时删除元素导致漏处理在for循环里直接del再append改变数组长度不要用删除思路改用双指针覆盖空数组越界直接访问nums[1]或类似下标处理len(nums) 1的情况或让循环天然覆盖空数组其中最容易犯的低级错误是“删除追加”。很多人觉得 Python 的list.remove(0)看起来挺方便的但它在内部要做一次线性查找找到后还要搬移后续元素。更麻烦的是遍历过程中删除元素会让列表长度不断变化很容易漏掉元素或者下标越界。这个坑我已经见过太多次了强烈建议直接放弃删除思路。4.2 如何快速定位逻辑错误如果代码跑出来不对我推荐用“打印慢指针”的方法排查。在循环里加几行日志把每一步的fast、slow和数组状态都打出来很快就能看出问题出在哪里。def move_zeroes_debug(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[fast], nums[slow] nums[slow], nums[fast] print(ffast{fast}, slow{slow}, nums{nums}) slow 1跑一次[0, 1, 0, 3, 12]如果打印结果显示slow在某些该停的位置没有停或者数组中间冒出多余的 0那基本就是自增逻辑写错了。排查算法题不需要什么高级工具最原始的打印法往往最快。4.3 面试官喜欢追问的变形题移动零这道题还有个英文版的后续提示能不能将总操作数最小化这本身就是一个追问点。但真正的面试中问题通常会以变形的方式出现常见的有下面这些第一“能不能只遍历一次”答案是交换法。这里考察的是你对覆盖法和交换法的理解深度如果只知道覆盖法可以主动补一句“还能用交换优化成一轮循环”面试官印象分会好很多。第二“如果数组里非零元素不一定是正整数可能是负数、字符串怎么改”答案很简单判断条件从! 0改为对应条件即可整个逻辑无需调整。这说明双指针关注的是“位置布局”和具体值没有强耦合。第三“把 0 移到末尾改成把偶数移到末尾保持奇数顺序怎么做”思路完全一样只是判断条件从nums[fast] ! 0变成nums[fast] % 2 ! 0。如果想更进一步区分奇偶并保持顺序那就是另一个话题了但移动零可以作为它的基础。第四“如果是链表怎么把所有值为 0 的节点移到末尾”这就不能照搬数组解法了因为链表没有随机访问快慢指针的下标概念失效。通常做法是遍历链表把非零节点拆出来接到新链上再把零节点拼接在尾部。虽然思路不同但“维护有效序列尾部指针”这个想法是一脉相承的。4.4 现场讲解代码的思路顺序面试时如果被问到这道题我建议按照这样的顺序讲先说暴力做法及其问题再说双指针的核心不变量最后写出覆盖补零版本然后提一句可以优化成交换法。这样既展示了分析能力又展示了代码能力还能自然引出复杂度分析。核心不变量一定要说出来slow左边都是已整理好的非零元素fast一直在探索未知区域。讲清楚这一句话面试官基本就能确认你真正理解了题目。5. 从移动零到双指针家族一题串起一片题5.1 双指针的三种常见模式移动零属于双指针里的“快慢指针”模式但双指针本身是一个大家族面试题里常见的有三种模式快慢指针、对撞指针、滑动窗口。快慢指针通常用于同向扫描一个指针走得快一个指针走得慢典型场景包括链表找中点、检测链表是否有环、数组原地去重。对撞指针则是两个指针从两端向中间逼近典型场景是两数之和、反转数组、判断回文、盛水容器。滑动窗口本质上也是同向双指针但两个指针之间的距离形成窗口用于求解子串或子数组问题。移动零是这三种模式里最好入门的一个因为它的指针职责非常清晰不涉及复杂的窗口维护也没有左右夹逼的边界讨论。把这个题吃透再去做删除有序数组重复项、移除元素这类题会发现套路几乎是同一个。5.2 和删除重复、移除元素一起刷一题三吃LeetCode 上有三道题可以放在一起刷26 删除有序数组中的重复项、27 移除元素、283 移动零。它们的核心模板完全一致都是“快慢指针 覆盖”区别只在于判断条件。题目核心判断条件处理方式26 删除有序数组重复项nums[fast] ! nums[slow]覆盖到slow 1slow自增27 移除元素nums[fast] ! val覆盖到slowslow自增283 移动零nums[fast] ! 0覆盖或者交换到slowslow自增末尾补 0我刷题那会儿经常是刷一道忘一道后来发现把这些同模板的题放一起对比记忆效率高很多。做完 283 之后再写 27 基本就是改两个字符的事写完 27 再看 26只需要多考虑一个“重复”条件。读懂这道题模板等于同时掌握了三道 LeetCode 简单题性价比极高。5.3 双指针思想在真实工程里的投影有人可能会想这种算法题除了面试实际工作里真用得上吗其实“原地压缩有效数据”是工程里非常常见的需求。举个例子在嵌入式设备或网络驱动里缓冲区是固定大小、预先分配好的内存块你不能随便新建数组。当一批事件中混入无效记录时最省内存的做法就是把有效记录统一搬到前面让后面的空间可以被复用这和移动零干的事一模一样只是把“0”换成了“无效事件”。再比如日志系统高并发环境下每一帧日志都不能随意 new 对象否则 GC 压力很大。我们需要在一个定长的日志缓冲区内把新写入的有效日志覆盖到旧日志前面预留出的位置这种场景本质上就是双指针的变体。理解了这个你才会真正明白为什么题目要求“原地修改、空间 O(1)”——在资源受限的真实系统里多分配一份数组有时候是不可接受的。最后说点个人体会。移动零这道题我前前后后刷过很多遍每次都会有新理解第一次只觉得覆盖法很妙后来才意识到它背后是“用一个不变量维护答案区域”再后来刷到三数之和、接雨水时发现对撞双指针又是另一套玩法。我现在的习惯是每学一道双指针新题就回来看一眼移动零的代码问自己三个问题慢指针维护了什么快指针在探索什么元素之间是否需要交换如果都能答上来说明这题真的吃透了。如果你刚开始刷题建议按 27 移除元素 → 26 删除有序数组重复项 → 283 移动零 的顺序连刷三题同一个模板用熟练之后再去做其他双指针题会轻松很多。