Leetcode 283『移动零』是我在算法入门阶段反复写过好几遍的一道题。先说结论如果你刚开始刷题这道题值得放进前二十题如果你准备面试这道题是数组双指针的经典敲门砖。它要解决的问题一句话就能说清——把一个数组里所有的 0 挪到末尾同时保持非零数字原来的先后顺序。真正难的不是看懂题而是能在不借助额外数组的前提下把这件事做干净并且跟面试官把每一步为什么这样写讲明白。我见过不少人把这道题背下来了代码写得飞快但被问到“slow 和 fast 各自代表什么”“为什么最后补零从 slow 开始”就卡住了。这篇笔记想把题目拆开揉碎从最朴素的思路逐步演进出最优解再把同类题串起来。不管你是刚接触算法的初学者还是准备面试想补齐短板的人都应该能从中拿到点东西。1. 题目到底在考什么1.1 把题面翻译成人话原题描述很简洁给定一个数组 nums请把所有 0 移动到数组末尾同时保持非零元素的相对顺序。举个例子输入: [0, 1, 0, 3, 12] 输出: [1, 3, 12, 0, 0]很多初学者看到这个输出会觉得是“排序把 0 放后面”其实不对因为非零元素之间的顺序完全没变1 还是在 3 前面3 还是在 12 前面。所以准确地说这是一个“稳定分区”问题按是否为 0 分成两类并且让原顺序稳定保留。题目描述里还有两个补充条件必须在原数组上操作不能拷贝额外的数组尽量减少操作次数。这直接封死了最偷懒的写法也决定了我们后面所有思路的走向。1.2 隐含的三条硬性要求我把这道题的隐含要求拆成三条每条都会影响解法选择。第一原地修改。意思是不能新建一个数组把非零元素装进去再把零补在后面然后把新数组返回。你只能操作传入的那个数组对象本身。这一点在很多语言的函数传参里都有坑Python 尤其容易踩后面我会专门讲。第二保持相对顺序。这就是“稳定”的含义。有些新手会用排序来做觉得“把 0 排到最后”就是答案但排序会破坏原本非零元素之间的相对顺序而且排序复杂度至少是 O(n log n)完全不是这题想要的东西。退一步说即便你用稳定排序也只是绕路不是正解。第三尽量少的操作次数。最理想的状态是遍历一遍数组就完成全部工作。这意味着算法要尽量做到每个元素只处理有限次整体复杂度控制在 O(n)。这也是面试官通常期待的标准解。1.3 为什么这道题在面试里被反复拿出来这道题难度不高但出现的频率一直很高。原因是它把几个基本功揉在了一起数组下标的运用、指针或者说索引的设计、原地算法的空间意识。真实场景里这种需求也不少见。比如一份用户行为日志事件类型为 0 表示无效事件需要把有效事件全部挪到数组前段同时保留事件的先后时间顺序再比如一批任务列表需要把已取消任务沉到末尾但不能改变正常任务之间的优先级顺序。只要你写过后端批处理大概率遇到过类似的分区需求。所以这道题看起来是刷题题实际上是一道披着算法外衣的工程题。它考察的不仅仅是你会不会写 for 循环而是你有没有“在有限空间里通过调整索引完成任务”的直觉。2. 新手最容易先想到的解法为什么我会劝你别急着写2.1 新建数组的做法思路对但不合格我刚刷这道题时的第一反应特别简单把非零元素挑出来记录有多少个 0然后组装一个新数组。def move_zeroes(nums): result [x for x in nums if x ! 0] result [0] * (nums.count(0)) nums[:] result这个解法是正确的跑示例也能过但完全不达标题的硬性要求它用了额外空间而且 nums.count(0) 又额外遍历了一遍数组。假如输入有 10 万个元素代码会在内存里多出一份近乎完整的数组数据量翻倍时开销也翻倍。如果题目没要求原地这个解法完全能用可面试场景下面试官几乎必然追问一句“能不能不用额外空间”。所以它只能作为理解题意的第一步不能作为最终答案。2.2 从 O(n) 空间到 O(1) 空间差别在哪从 O(n) 空间降到 O(1) 空间听起来只是复杂度标识变了实际带来的约束差异非常大。O(1) 空间意味着除了若干个变量你不能和输入规模挂钩地申请内存。数组元素个数越多你越不能复制一份同样大小的数据。这在真实系统里很关键内存是有限资源尤其在嵌入式、游戏客户端、高并发服务端里一次多余拷贝可能直接影响延迟和吞吐。这里要特别提醒 Python 初学者一个坑函数内部写nums result和写nums[:] result效果完全不同。nums result只是让函数内部的局部变量指向了新的列表函数外部的原数组没有任何变化nums[:] result才是把原列表对象的内容整体替换成 result 的内容。如果你在本地测试时直接在全局作用域写可能看不出区别一旦封装成函数就出问题。2.3 决定用双指针前先想清楚这几件事在我自己把解法最终优化到双指针之前我先问了自己几个问题第一0 到底需不需要被逐个搬运到末尾其实不需要。我们只要把非零元素全部前移剩下的位置统一填 0 就可以了。0 本身没有“顺序”需要保持所以它们内部怎么排列都无所谓。第二能不能让每个元素只被读取一次如果能做到那就已经是 O(n)。能不能每个非零元素只被写入一次如果能做到那操作次数就非常少。第三用什么手段记录“下一个非零元素该放的位置”这个位置会随着扫描不断推进天然适合用一个变量来维护。想清楚这三点双指针的思路就不难自己推导出来一个指针负责向前扫描、寻找非零元素另一个指针负责标记写入位置。3. 双指针覆盖法从最朴素的实现开始3.1 双指针的灵魂快慢指针各管一摊双指针在很多数组题里是万能钥匙但理解它不能只记住模板要记住两个指针各自的职责。在这道题里我习惯把两个指针叫slow和fast。slow下一个非零元素应该放置的位置也是当前前段有效区的右边界。fast当前正在扫描的数组位置负责一路往右寻找非零元素。打个比方你在整理一排书架fast是你正在检查的书slow是接下来要把有效书放过去的空格。每遇到一本不该淘汰的书你就把它放到slow指向的空位然后slow往后挪一格遇到 0 就直接跳过继续往后检查。3.2 核心代码逐行分析这是覆盖法最朴素的 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表示当前没有任何非零元素被安置所以第一个非零元素应该放到下标 0。for fast in range(len(nums))让快指针从 0 开始扫描到数组末尾。每一次循环fast就是“当前读取的位置”。进入循环后如果nums[fast] 0说明当前元素是应该被沉底的零直接跳过不做任何操作。slow不动后面遇到非零元素时仍然可以写到这个空位。如果nums[fast] ! 0就执行nums[slow] nums[fast]把非零元素往前搬运到slow指向的位置。然后slow 1表示“下一个空位”已经向右移动。第一个循环结束时所有非零元素都已经按原顺序放到了数组前段slow恰好等于非零元素的个数。接下来第二个循环从slow开始到数组末尾全部填 0。这里的核心思想是先做“非零前移”再做“末尾补零”。零元素不需要真的和谁交换位置最后统一覆盖即可。3.3 复杂度为什么是 O(n) 和 O(1)第一个循环最多执行 n 次第二个循环最多执行 n 次合起来最多 2n 次操作。常数 2 不影响复杂度级别所以时间复杂度是 O(n)。空间上除了slow和fast两个整数变量没有额外申请和数组规模有关的存储所以空间复杂度是 O(1)。对比一下新建数组法那个做法除了最终结果数组外还涉及 Python 内部列表推导的临时结构空间是 O(n)。在数据规模很大时这两种做法对内存的压力完全不同。3.4 覆盖法的坑什么时候需要补零覆盖法最容易被忽略的一点是第二个循环到底应该从哪个下标开始补零。很多人写成for i in range(fast, len(nums))这是一个典型错误。因为fast在循环结束时指向的是数组最后一个位置并不代表“有效区的右边界”。真正代表有效区右边界的是slow只有它知道有多少个非零元素被放到了前面。什么时候第二个循环实际上什么都不用做答案是原数组里没有 0 的时候。比如输入[1, 2, 3]第一个循环会把每个元素写到自己位置上slow走到 3range(slow, len(nums))是空区间补零操作自然跳过。换句话说补零的区间长度正好等于 0 的个数。slow到数组末尾的距离就是数组中 0 的数量所以从slow开始补零一定是准确的。4. 扩展与进化把“覆盖”升级成“交换”的经典实现4.1 为什么最终代码可以短到三五行覆盖法的思路很清晰但代码里有两个循环。还有一种写法更简洁用一次遍历加交换完成很多热门题解就是这种def move_zeroes(nums): j 0 for i in range(len(nums)): if nums[i] ! 0: nums[j], nums[i] nums[i], nums[j] j 1核心是j维护“第一个 0 的位置”i负责向后扫描。遇到非零元素就把它和j指向的 0 交换然后j前进一位。这样做的好处是省掉了最后补零的循环。交换本身会把 0 自动带到后面不需要再单独写第二个循环。代码短一截逻辑也更紧凑。我第一次看到这个写法的时候第一反应是“这么简单还能对吗”。后来在草稿纸上推演了几轮才彻底放心它背后其实和覆盖法是同一套思想只是把“先前移后补零”变成了“边扫描边交换”。4.2 相对顺序是怎么保住的为什么交换不会打乱非零元素的顺序因为i是严格从左往右扫描的每次遇到一个新的非零元素它总是被放到j当前指向的位置。而j的位置只会被非零元素占据且每写一个就右移一格所以非零元素的写入顺序和扫描顺序完全一致前面出现的非零元素永远不可能被后面出现的非零元素越过。你可以这样理解这个交换不是随意的交换它本质上是把“遇到的非零元素”逐个放到前段连续空位上和覆盖法一模一样。只不过覆盖法把被覆盖位置的旧值先忽略了最后补零交换法则把旧值通常是 0换到后面去顺手完成了填零。这里要留意一个特殊情况当数组里没有 0 时i和j同步移动每次交换都是元素和它自己交换数组最终不变。所以这个写法天然兼容“无 0”和“全 0”的边界情况。4.3 几个边界用例的手推过程我用示例数组手推一遍你就更能感受到指针是怎么走的。输入[0, 1, 0, 3, 12]初始j 0。i 0nums[0]是 0跳过j仍是 0。i 1nums[1]是 1交换nums[0]和nums[1]数组变成[1, 0, 0, 3, 12]j 1。i 2nums[2]是 0跳过。i 3nums[3]是 3交换nums[1]和nums[3]数组变成[1, 3, 0, 0, 12]j 2。i 4nums[4]是 12交换nums[2]和nums[4]数组变成[1, 3, 12, 0, 0]j 3。再看一个边上例子[0, 0, 1]初始j 0。i 0跳过。i 1跳过。i 2遇到 1交换nums[0]和nums[2]数组变成[1, 0, 0]。一次交换就完成了任务。再看无零情况[1, 2, 3]i每次都与j相等和自己交换数组从头到尾不变。这说明交换法的额外操作在无零时只是一些无效自交换但不影响结果也不会报错。5. 同类题目串讲这套思路还能打哪些题5.1 Leetcode 27 移除元素是同一个骨架做完移动零以后我建议你马上去看“移除元素”这题。题目描述是给定数组nums和目标值val原地移除所有数值等于val的元素返回移除后数组的新长度。最标准的解法长这样def remove_element(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow和移动零的覆盖法几乎逐字相同。区别只有两点判断条件从! 0变成了! val不需要补零因为题目只要求返回新长度对数组末尾的值没有要求。很多人会这样记这道题背后是同一个“筛选保留元素并前移”的模板。你要保留什么就把保留条件写在if里然后用slow维护写入位置fast负责全量扫描。5.2 Leetcode 26 删除有序数组中的重复项也是同一个骨架再往深走一步看“删除有序数组中的重复项”这题给定一个有序数组原地删除重复出现的元素使每个元素只出现一次返回新长度。解法还是快慢指针def remove_duplicates(nums): slow 0 for fast in range(len(nums)): if fast 0 or nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow这里的变化是保留条件从“不等于某个值”变成了“不等于前一个被保留的值”。因为数组有序重复元素必然相邻所以每次只需要跟nums[slow - 1]比较就能判断当前元素是不是一个新的、应该保留的值。这三道题放在一起看你会发现核心模板是一致的一个指针向后扫描一个指针维护写入位置。变的是保留条件。移动零保留非零移除元素保留非 val去重保留首次出现的新值。5.3 再扩大一个视野同向双指针和对撞双指针是两回事经常看到有人把双指针所有题目混在一起记这是新手比较容易绕晕的地方。其实双指针至少可以分为两大类。一类是同向双指针也就是这一篇讲的两个指针都从左往右移动比如移动零、移除元素、去重。这类问题通常要求保持元素间的原始相对顺序或者处理单调有序数组的扫描。另一类是对撞双指针两个指针一个从左边开始往右走一个从右边开始往左走比如有序数组的 Two Sum、盛最多水的容器。这类问题通常依赖数组的某种有序性在两端向中间逼近答案。我自己的体会是看到“保持相对顺序”或者“原地筛选”这几个字优先想同向双指针看到“有序数组”并且要求找满足条件的两个元素优先想对撞指针。把这两大类分开记忆比单独背某道题的题解要高效得多。6. 常见错误与调试实录6.1 我见过的高频错误这道题代码量少但出错率并不低。我帮人 review 代码时反复看到下面几类问题。第一补零起点写错。覆盖法第二个循环写成for i in range(fast, len(nums))结果把还没扫描完的后续元素给清掉了。记住slow才是有效区边界fast只是最后停在了数组的最后一个位置它的值不能代表非零元素个数。第二交换法的j更新逻辑混乱。比如在nums[i] ! 0时只写了j 1忘记交换导致非零值被丢弃。正确的记录是只要发现非零就执行交换然后j 1遇到零时什么都不做。第三Python 特有的传参问题。函数内部写了nums [x for x in nums if x ! 0] [0] * (nums.count(0))看起来是在修改其实只是改了函数局部变量。外部数组纹丝不动测试永远失败。处理办法是用切片赋值nums[:] ...或者走真正的双指针原地修改。6.2 必跑的测试用例清单我很喜欢在写完数组题后跑一遍边界用例比直接提交省时间。这道题我建议至少跑这些[] - [] [0] - [0] [1] - [1] [0, 0, 0] - [0, 0, 0] [1, 2, 3] - [1, 2, 3] [0, 1, 0, 3, 12] - [1, 3, 12, 0, 0] [1, 0, 2, 0, 3, 0] - [1, 2, 3, 0, 0, 0] [3, 0, 2, 0, 1] - [3, 2, 1, 0, 0]其中空数组、单元素、全零、无零这四类最容易暴露边界问题。我实际调试时通常会写一个小脚本把上面的用例存成列表然后用assert批量断言这样每次改完都能秒级确认没有引入新问题。6.3 写这道题时的几个好习惯写双指针题我现在养成了几个固定习惯对刷其他题也适用。第一写代码前先在注释里写清指针含义。哪怕只是两句比如“slow 表示下一个写入位置fast 表示扫描位置”。不要觉得这多余它能帮你避免写着写着就把变量含义搞混。第二命名用slow和fast尽量不要用i和j。i和j太抽象双方交流时还要额外解释slow和fast一看就知道谁是写指针、谁是读指针。第三写完后口头给自己讲一遍边界情况。我会指着代码说“如果没有 0slow 会跟 fast 同步走到末尾补零区间为空如果全是 0slow 一直停在 0最后整个数组原地补零”。能讲清楚这两句话这道题才算真的懂了。第四从覆盖法理解但提交前用交换法再巩固一遍。两段代码花不了几分钟但能让你对“先前移后补零”和“边扫描边交换”两种实现都有手感。面试时你甚至可以说出两种方案并解释为什么交换法代码更短。这道题我刷了很多遍每次重刷都有一点新的收获。如果只能留下一句话我会说写双指针之前先在注释里写清楚每个指针的意义代码只是把注释翻译成语法而已。后面你还会遇到 Leetcode 27、26、80 这些同源题目都可以回到这个骨架来对照。希望这篇笔记能帮你把移动零彻底吃透也把双指针的思维基础打牢固。