LeetCode 283 移动零:双指针原地操作,数组算法题的经典套路 在LeetCode和各类公司的算法题库里我的职业是帮你把这道题讲透所以你直接把我这段话当成正文开始前的引子就行。移动零Move ZeroesLeetCode 283是我在技术面试现场见到频率最高的数组原地操作题之一。题目本身很短给定一个数组nums把所有 0 移动到数组末尾同时保持非零元素的相对顺序并且必须原地操作不能复制数组。很多第一次刷到它的人觉得简单但真到写代码的时候会出现各种奇怪的问题有人用splice会导致数组长度动态变化、有人写出了 O(n²) 的写法还不自知、有人把“原地操作”理解成“可以新建一个数组再赋值回去”。这篇文章我就把这道题从审题、暴力解、双指针推导、最优解到同类题串讲完整拆一遍把这个被称为“数组原地操作敲门砖”的题目彻底讲明白。1. 题面解读一道简单题为什么被公认经典这道题之所以被放在“每日一题”或入门列表里不是因为算法有多难而是因为它把数组操作里最核心的几个考点全占了相对顺序保持、原地空间约束、线性时间复杂度、边界条件处理。先看原题给定一个数组nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意必须在不复制数组的情况下原地对数组进行操作。示例输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0]就这么两句话。但拆开看每个字都是考点。1.1 “保持非零元素的相对顺序”意味着什么这句话换一个说法就是这个操作必须是“稳定的”。如果你对排序算法的稳定性有概念就会知道稳定意味着相同类别的元素之间的先后关系不能变。放到这道题里[0,1,0,3,12]里的 1、3、12 原本是 1 在 3 前面、3 在 12 前面移动之后 1、3、12 依然要保持这个顺序不能变成[12,3,1,0,0]。可能有人会问这些都是整数相等的数字看起来不都一样吗顺序乱了为什么不行这是因为在真实工程里数组里的元素往往不是裸值而是一组对象的某个字段。比如一个订单列表按时间排序你想把状态为“已取消”的订单移到末尾这时候每个订单还有订单号、金额等属性整个对象必须跟着字段一起移动而且相对顺序不能乱。如果把接口的返回结果顺序打乱前端展示就错乱了。所以“保持相对顺序”不是形式要求而是一个实用性约束。1.2 “原地操作”才是整道题的灵魂LeetCode 上有一句话Do not allocate another array for this purpose。意思是不要为这个操作分配另一个数组。这是真正的限制条件。如果允许新建数组这道题的难度会直接降到“一句话能写完”的水平def move_zeroes_simple(nums): # 非原地仅用于理解思路不能用在这道题 return [x for x in nums if x ! 0] [0] * nums.count(0)但问题在于很多人在实际业务里写代码时完全意识不到“复制数组”带来的空间开销。一个 10 万元素的数组你用filterconcat或者append新列表内存峰值会翻倍。虽然现代服务器内存很廉价但在处理大规模数据、嵌入式环境或者移动端时空间复杂度 O(n) 的解法可能就是不可接受的。面试里考察“原地操作”倒不完全是抠空间而是看你能不能在一个受限环境下通过下标和指针的精细控制完成数据搬移。这更贴近底层逻辑和真实性能敏感场景。三种典型解法的复杂度对比我放在这里后面会逐个展开解法时间复杂度额外空间复杂度是否符合题目要求暴力移除再追加O(n²)O(1)时间不达标复制非零元素到新数组O(n)O(n)空间不达标双指针覆盖法O(n)O(1)达标双指针交换法O(n)O(1)达标很多人一上来就直接写第四个这没问题但如果面试官追问“你能说说为什么不能用第二个思路”答不上来就说明只是在背题。2. 我见过的失败解法为什么这些“直观做法”都差点意思算法题的难点往往不在于最优解有多难而在于最简单直白的思路里藏着陷阱。移动零这道题我见过至少三种失败的尝试每种都对应一类新手常见的错误认知。2.1 暴力法边找零边删除时间复杂度爆表最朴素的思路是遍历数组遇到 0 就把它删掉然后再在数组末尾补一个 0。用 JavaScript 写很容易变成这样// 反面教材时间复杂度 O(n^2) const moveZeroes function(nums) { for (let i 0; i nums.length; i) { if (nums[i] 0) { nums.splice(i, 1); nums.push(0); i--; // 纠偏因为 splice 会改变数组长度和索引 } } };这个写法表面看没问题但splice在数组中间删除一个元素时后续所有元素都要往前移动一位底层的内存移动代价是 O(n)。如果数组里有一半是 0最坏情况下总复杂度会变成 O(n²)。这还没算i--这种“纠正索引”的操作写多了之后代码很难维护。在 Python 里对应的坑是用list.remove(0)循环删除remove本身也是 O(n) 的查找加搬移和splice一个道理。这类写法的优点是空间是 O(1)缺点是用“删除”这个操作来制造移动代价太高。做面试题时还有一个隐藏问题很多语言内置的删除操作会动态调整数组长度导致你在遍历过程中修改数组结构进而引发各种诡异的逻辑错误。我见过有人用 Java 的ArrayList.remove在for-each循环里删元素直接抛ConcurrentModificationException。这是工程上的经典教训不要在迭代过程中修改容器结构。2.2 额外数组法思路清晰但直接违反题目要求如果允许额外空间最直观的解法是遍历一遍原数组把所有非零元素按顺序放入一个新数组最后补零# 反面教材额外空间 O(n) def move_zeroes_non_inplace(nums): result [x for x in nums if x ! 0] result [0] * (len(nums) - len(result)) return result这个解法时间复杂度是 O(n)思路也非常清晰但面试里如果只写这个通常会被判为不合格因为题目明确要求“原地操作”。我在面试候选人的时候如果有人先口述这个解法作为“最基础思路”我会觉得他分析能力不错但如果他直接提交这段代码并表示“已经做完了”我会认为他没有认真读题或者没有理解空间约束的意义。这种“能跑但不符合约束”的解法在真实业务里其实更常见——先复制一份再处理虽然代码简单但内存翻倍、耗时增加而且原数组根本没变调用方期望的副作用没有发生。2.3 sort 排序看起来取巧实际上是不稳定还有人会想到既然要把 0 放最后那我把数组按某种规则排序不就行了比如 JavaScript 里可以写// 反面教材不稳定且容易出现意外行为 nums.sort((a, b) (a 0) - (b 0));先不说这个排序谓词在Array.prototype.sort稳定性的版本差异下表现如何就算法原理而言sort的绝大多数实现时间复杂度是 O(n log n)比双指针的 O(n) 更慢。而且排序通常是不稳定的或者依赖具体环境实现如果用这个方式非零元素很可能就不保持原有顺序了。移动零本质上是一个“分区问题”不是“排序问题”用排序这个重武器去解决一个轻量需求方向就错了。3. 双指针思路是怎么一步步演化出来的在正经讲解最优解之前我想把思考过程完整还原一遍。因为很多题解直接甩出双指针代码看懂了但记不住能记住的只有推演过程。3.1 从“搬书”的物理直觉出发想象一个书架上面放了一排书其中夹杂着一些灰尘袋代表 0。你的任务是把所有灰尘袋移到书架的右侧书保持原有顺序。你会怎么做一个自然的动作是拿一个空位指针左手从最左边开始准备接收书再拿一个扫描指针右手从左往右扫过去。右手每发现一本真书就把它放到左手指向的位置然后左手向右挪一位。等右手扫到书架尽头左手左边的位置已经全是书了剩下的位置自然就是灰尘袋——把它们填上灰尘袋0即可。这个动作就是双指针覆盖法的物理原型。很多人学算法的时候觉得指针抽象其实它就是模拟“一个人在整理一排东西”的过程一个指针表示“下一个可放置的位置”另一个指针表示“正在检查的位置”。3.2 循环不变式为什么覆盖法能保证正确写算法题尤其是这种几行代码就能写完的题不能只靠“试一下没错”来证明正确性。双指针覆盖法可以用“循环不变式”来严格论证在每轮循环开始前left左边不含left的所有元素都是非零的并且它们保持了原数组中的相对顺序。left本身指向“下一个非零元素应该写入的位置”。right左侧到left右侧之间的区域是已经被扫描但暂时不关心的元素可能是 0也可能是已经处理完的。开始时left 0左边没有元素条件成立。每轮循环中如果nums[right] ! 0我们把它写入nums[left]并让left加一因为right是从左到右遍历的所以写入位置始终不会早于扫描位置元素顺序天然保持。循环结束时left之前全是非零元素之后的位置未覆盖到需要手动补零。这段逻辑看起来简单但它其实是一个严格的数学归纳。你在面试时如果能这样解释“为什么你的代码是对的”会比只报一个“Accepted”高一个档次。4. 双指针覆盖法最直白的原地解法逐行拆给你看现在进入核心代码。覆盖法分两步走第一步把非零元素全部搬到数组前部第二步把剩余位置全部置零。4.1 用 Python 写覆盖法以及nums[:]的微妙之处from typing import List def move_zeroes(nums: List[int]) - None: Do not return anything, modify nums in-place instead. left 0 # 下一个非零元素应写入的位置 # 第一轮搬运所有非零元素 for right in range(len(nums)): if nums[right] ! 0: nums[left] nums[right] left 1 # 第二轮把剩余位置全部置零 for i in range(left, len(nums)): nums[i] 0这里有一个几乎所有 Python 新手都会踩的坑如果你在 LeetCode 的函数里写的是nums [x for x in nums if x ! 0] ...那么函数体里的nums已经指向了一个新的列表对象外部传入的数组完全没有被修改。因为 Python 函数参数是“对象引用传递”但重新赋值会改变局部变量的绑定关系。所以题目里要求“原地修改”你要么用nums[:] ...这种完全切片赋值要么就用下标逐个改。我上面这段代码用的是下标逐个改这也是我觉得最稳妥的写法。4.2 JavaScript 版覆盖法不要在遍历时调用 splice 或 pushJavaScript 的等价实现如下const moveZeroes function(nums) { let left 0; for (let i 0; i nums.length; i) { if (nums[i] ! 0) { nums[left] nums[i]; left; } } for (let j left; j nums.length; j) { nums[j] 0; } };你可能会问这里为什么不用forEach因为我们不需要在遍历时修改元素数量只需要修改元素值forEach也能做到。但很多人在第一版代码里写的是splice加push这在第 2.1 节我已经分析过会造成 O(n²)。用下标for循环可以让你清楚地知道数组长度不会变化指针移动完全可控。还有一个细节JavaScript 的数组虽然可以动态增长但在这道题中我们从头到尾都没有改变数组长度这符合“原地操作”的严格定义。有些语言如 Java 的ArrayList可能还会涉及容量和装箱但思路完全一样。4.3 C 语言视角用指针写一遍会更清楚再看 C 语言实现。C 没有现成的“数组对象”只有裸内存这反而能帮助你理解指针的本质void moveZeroes(int* nums, int numsSize) { int left 0; for (int right 0; right numsSize; right) { if (nums[right] ! 0) { nums[left] nums[right]; left; } } for (int i left; i numsSize; i) { nums[i] 0; } }C 版本里nums[left]的本质是*(nums left)nums是指向数组首元素的指针下标运算就是指针偏移。这里不需要动态分配内存因为所有的操作都在原内存块上完成。我在带新手时发现一个有趣现象用 C 练过指针的人回头写 Python 或 JavaScript 的双指针会非常有感觉因为他们能把抽象的“指针/下标”翻译成内存地址的移动比如left是“当前位置”right是“扫描位置”。4.4 边界用例写完之后至少要测这几组要确保覆盖法正确至少用以下用例自测[] // 空数组不崩不跑 [0] // 一个 0 [1] // 一个非零 [0,0,0] // 全是零 [1,2,3] // 全是非零完全不动 [0,1,0,3,12] // 标准示例 [1,0] // 非零在零之前覆盖法在这些用例下都成立。最大的风险在第 4.1 节说的“第二步补零被省略”——如果只做第一步测试[1,2,3,0,0]这种本来就是非零在前的用例你是看不出问题的但一遇到[0,1,0,3,12]末尾就会出现残留的 3 和 12。所以自测用例一定要故意包含零和非零交替的情况。5. 更优雅的解法双指针交换法一步到位覆盖法思路直观但需要第二轮补零总觉得不够利索。交换法可以做到只遍历一遍不需要后处理并且每一步都保持着“数组整体仍然由原来的元素构成只是位置变了”的不变性。这也是很多官方题解推荐的第一写法。5.1 覆盖法和交换法本质区别在哪先看代码Pythonfrom typing import List def move_zeroes(nums: List[int]) - None: left 0 for right in range(len(nums)): if nums[right] ! 0: nums[left], nums[right] nums[right], nums[left] left 1然后看 JavaScriptconst moveZeroes function(nums) { let left 0; for (let right 0; right nums.length; right) { if (nums[right] ! 0) { [nums[left], nums[right]] [nums[right], nums[left]]; left; } } };核心逻辑只有几行left指向“当前第一个 0 的位置”right负责扫描。扫描到非零元素时把它和left指向的 0 交换然后left加一。看起来和覆盖法很像但有一个关键区别覆盖法是“直接覆盖非零元素到前面”会丢掉原本位置上的值所以第二轮必须补零。交换法是“把非零元素和 0 交换”所有元素始终都在数组中只是位置交换所以不需要后处理。可以这样理解覆盖法是“挪书”把书抽出来放到前面原来的空位最后统一放灰尘袋交换法是“顺手把灰尘袋向后抛把书换到前面”扫完一遍灰尘袋自然全部沉到末尾。对比一下对比维度覆盖法交换法第二轮补零需要不需要写操作的次数每个非零元素只写一次最优每个非零元素可能交换两次但常数级差异可忽略循环不变式left 左侧全是非零右侧未处理left 左侧全是非零left 到 right 之间全是 0right 右侧未处理代码可读性很好理解稍作思考也能接受写法更简洁从指令层面看交换法的赋值次数是覆盖法的 2~3 倍但对这道题来说影响非常小。实际选择哪个我觉得取决于你更看重可读性还是更在乎常数级的性能。如果是在面试里我更推荐交换法因为少一个边界点也不容易漏步骤。5.2 手动模拟交换过程看一次就懂拿标准示例[0,1,0,3,12]模拟一下初始状态nums [0, 1, 0, 3, 12], left 0, right 0 right0nums[0]0跳过。 right1nums[1]1非零交换 nums[0] 和 nums[1]。 得到 [1, 0, 0, 3, 12]left 变成 1。 right2nums[2]0跳过。 right3nums[3]3非零交换 nums[1] 和 nums[3]。 得到 [1, 3, 0, 0, 12]left 变成 2。 right4nums[4]12非零交换 nums[2] 和 nums[4]。 得到 [1, 3, 12, 0, 0]left 变成 3。 遍历结束。注意一个细节当left和right指向同一个位置时交换操作相当于元素和自己交换结果不变。无论是 Python 的元组解包还是 C 的临时变量交换这种情况下都不会出错不需要额外加if (left right) continue这种保护。有的新手会担心数组越界但left永远小于等于right因为left只在遇到非零时递增且最多递增到right不会出现left越界的可能。5.3 C 语言交换法的两个写法用下标写很简单但 C 里也常写成指针形式void moveZeroes(int* nums, int numsSize) { int left 0; for (int right 0; right numsSize; right) { if (nums[right] ! 0) { int tmp nums[left]; nums[left] nums[right]; nums[right] tmp; left; } } }如果写成指针void moveZeroes(int* nums, int numsSize) { int* left nums; // 指向当前零位置 int* cur nums; for (; cur nums numsSize; cur) { if (*cur ! 0) { int tmp *left; *left *cur; *cur tmp; left; } } }两种写法完全等价nums[i]在 C 中就是*(nums i)下标只是指针运算的语法糖。用指针书写的时候要特别小心cur nums numsSize这个结束条件指针越过数组末尾是未定义行为但只要循环条件这样写就没问题。6. 从移动零到一类题数组原地操作的通用套路移动零刷完之后你会发现很多题都是在玩同一个套路快慢指针读写指针。我把这个套路提炼出来以后遇到“在原数组上做某种条件分区”的题你都可以往这个框里套。6.1 读写指针的通用框架把right理解成“读指针”它负责往前走逐格检查把left理解成“写指针”它指向下一个可以被覆盖或交换的位置。这个框架的通用写法如下def partition_in_place(nums): left 0 for right in range(len(nums)): if 条件(nums[right]): # 把满足条件的元素放到前面 nums[left], nums[right] nums[right], nums[left] # 或 nums[left] nums[right] left 1 # 视题目要求决定是否需要后续步骤 return left # 返回值代表“前部分的有效边界”所谓“条件”可以任意替换条件为x ! 0就是移动零。条件为x ! val就是 LeetCode 27 移除元素。条件为x % 2 1把奇数放前面偶数放后面。条件为“和上一个元素不同”处理后就是删除排序数组中的重复项LeetCode 26。甚至 LeetCode 75 颜色分类也是这个框架的变体只是多了一个指针用三指针同时维护 0、1、2 三个分区的边界。6.2 同类题对比从移动零到三指针颜色分类我整理了一个简单的同类题对比方便你形成自己的刷题地图题目分区规则指针数量与移动零的关系283 移动零非零在前零在后2基础原型27 移除元素不等于 val 的在前2条件替换为! val26 删除排序数组中的重复项每个元素只保留一个2条件替换为值变化905 按奇偶排序数组奇数在前偶数在后2条件替换为% 275 颜色分类0、1、2 三色分区3移动零的升级版两轮快慢指针合并刷完移动零之后再去做移除元素你会发现代码几乎不需要怎么改只需要把nums[right] ! 0改成nums[right] ! val然后把left返回值带出来即可。我在带新人时经常说数组原地操作题本质上就是“给一个条件把满足条件的元素往数组前部收拢”双指针是这套动作的万能骨架。6.3 别被热搜词带偏原地操作只是数组题的起点最近网上关于数组的热搜词很多从 vba 数组、python 数组切片到指针数组、二维数组、树状数组、json 数组范围很广。移动零属于数组操作里最基础的一类但又有别于那些“处理数据结构”的数组题比如树状数组用的是数组来模拟树结构二维数组其实是一维数组的数组。它们各自的难点不同底层却共享一个基本功你对自己的数组内存布局、索引移动、边界条件是否足够敏感。我还看到有人在问“js 怎么取出数组中的某一段”“python 数组切片命令”这类基础问题说明很多人的数组基本功还没到位。移动零这道题说到底是给这些基本功做一次体检如果你能用下标操作、能控制循环边界、能不借助内置删除方法完成数据搬移那你的数组基础就合格了。至于那个“给定一个由 2n 个正整数组成的数组 a舍弃两个元素后两两配对使 gcd 大于 1”的题就是另一类数组排列组合的问题了考察的是数学构造和枚举能力和移动零不在一个赛道但同样要求你有数组思维。6.4 不同语言原地操作的具体坑位最后总结一下各语言在写移动零时常见的坑这些是我实际写代码时撞过墙才记住的Python函数内nums ...不会修改外部数组必须用nums[:] ...或者逐下标赋值。nums[:] [x for x in nums if x ! 0] [0] * nums.count(0)这种写法虽然建了临时列表但最终赋值给原切片对外是满足“原地”语义的。可是这里创建临时列表的空间开销还是 O(n)如果面试官较真还是要避开。JavaScript不要在forEach或普通for循环里用splice改长度会导致索引错位。如果要写交换用解构赋值[a[left], a[i]] [a[i], a[left]]很简洁但要注意这是 ES6 语法。Javaint[]是引用类型函数内直接改下标没问题但如果你用Arrays.stream(nums).filter(...)生成新数组就是额外空间。数组判空用nums null || nums.length 0否则可能NullPointerException。C数组参数传入函数后退化为指针sizeof拿不到数组长度所以题目会额外传numsSize边界条件必须写在循环里靠语言本身不会帮你拦越界。C可以用std::vector配合std::partition或std::remove都能实现但很多教程题解为了展示原理还是让你手写双指针。7. 我刷这道题踩过的坑和面试时的答法建议最后一部分我不讲新解法了聊点刷题和面试的实在经验。7.1 三个只有实际跑过测试才会遇到的隐蔽问题第一个坑是覆盖法漏掉第二步补零。我记得第一次自己写移动零的时候兴致勃勃写完非零搬运看了输出觉得挺对结果拿[0,0,1]一测就发现末尾的 0 没补到位。很多时候我们看题解觉得覆盖法“先搬再补”很自然但自己写的时候很容易只写第一部分就开始自测而测试用例如果恰好是[1,2,3]这种没有 0 的确实测不出来。所以我后来养成了一个习惯每道数组题都至少准备三组极端用例空数组、全相同元素、交替出现目标元素。第二个坑是 JavaScript 的splice在循环中改变数组长度。这个问题在力扣评论区出现频率极高很多人用for (let i 0; i nums.length; i)配合splice但每splice一次长度就变了nums[i]的下标就会跳过下一个元素。比如[0,1,0,3,12]i0 时删掉一个 0 后数组变成[1,0,3,12]i 变成 1正好指向 0删掉后变成[1,3,12]i2 指向 12结束最后 push 两个 0得到[1,3,12,0,0]。看起来很幸运但换成[1,0,0,2]就会出错。这类“动态改结构导致索引错位”的 bug 非常隐蔽最好的规避方法就是能用下标定长遍历就别在循环里改长度。第三个坑是测试用例只有[1]、[0]这种极短数组。这类用例能让代码通过但体现不出任何算法意图。我平时在力扣上自测一定会加[0,0,1,0,0,2,0]这种多零交错的长用例还手动 debug 看过每一轮指针的变化才能真正确认自己懂了而不是背了答案。7.2 面试现场答这道题的节奏建议如果面试官现场让你写移动零我个人建议按这个节奏走先别急着写代码用 10 到 20 秒复述一遍题目的约束保持相对顺序、原地操作。主动给出第一种思路如果不考虑空间可以先收集非零再补零但空间是 O(n)然后立刻说明因为题目要求原地所以我们要优化成双指针。讲双指针思路的时候用一句话说清楚“一个指针记录写入位置一个指针负责扫描”。写代码。写完不要马上说“完成”而是用示例数组口头走一遍循环指出left和right的移动过程。主动说时间和空间复杂度都是 O(n) 和 O(1)并说明交换法为什么不需要补零。这套节奏看似简单但能完整走完的人不多。很多人要么沉默地写完代码就停住了要么上来直接背最优解却不解释推导过程这两种在面试官看来都等于没答好。7.3 为什么“简单题”更值得反复刷移动零这道题是我带新人刷题的第一周必练题目之一。坦白说它不难但正因为它不难才能把注意力完全集中在“数组操作的基本功”上。每次写完代码我都会问自己三个问题我有没有在循环里修改数组长度我有没有破坏非零元素的相对顺序我的额外空间是不是 O(1)这三个问题如果都能斩钉截铁地回答“没有”那这道题才算真正掌握。刷到后面你会发现同样的三句话可以套用到移除元素、删除重复项、奇偶排序上。到最后做题的意义已经不是“会写这道题”而是“看到任何数组原地操作的题自然知道下一步该看哪个指针”。我自己在这种基础题上反复练了很久收益远比刷一百道偏题怪题要大——基本功这东西骗不了人。