最近一次模拟面试里我让候选人A写那道某在线题库里的经典题“移动零”。题目描述不长给定一个数组把所有的0移动到数组末尾同时保持非零元素的相对顺序要求在不复制数组的前提下原地完成。A同学三十秒交出答案遍历原数组把非零元素挑出来再在结尾补上若干个0。我追问了一句“那你申请的新数组放在哪了”他盯着屏幕愣是三分钟没动手。这道题在题库里标的难度是“简单”但在我这些年参与技术评审和带新人的经历里它恰恰是最容易翻车的一道。不是候选人不会写而是很多人把它当成了“删除零元素再补零”的字符串题完全没意识到题目里那句“原地”才是真正要考的东西。这篇文章我想把这道题掰开揉碎讲讲从直觉解法到最优解法的思维升级过程。它背后藏着一种在整个算法训练里都极其重要的能力把模糊的需求翻译成精确的指针语义。1. 一道“送分题”怎么成了面试翻车重灾区1.1 题目本身有多简单先把需求拆干净给定一个数组 nums例如 [0, 1, 0, 3, 12]要求输出 [1, 3, 12, 0, 0]。就这么点事。但题目里其实藏着三个隐性约束少看一个解法就会变味不复制数组原地操作只能在这一个数组的内存空间里做文章非零元素的相对顺序不能变1 必须在 3 前面3 必须在 12 前面尽量减少操作次数不是“能跑就行”而是要在时间复杂度和赋值成本上都有交代。“保持相对顺序”这条最容易被轻视。我见过有人一看到移动零马上想到左右双指针左指针找0右指针找非零然后交换。这个思路用在快速排序的partition上没问题但用在这里会出事。比如数组 [1, 0, 0, 2]左边指针指向下标1的0右边指针从末尾找到下标3的2交换后变成 [1, 2, 0, 0]看似正确但再来一个例子 [0, 0, 1, 2]左边找到下标0的0右边找到下标2的1交换后变成 [1, 0, 0, 2]非零元素1跑到2前面去了相对顺序被破坏。这就是“简单题”的陷阱。需求有三个约束缺一个看起来也能跑但面试官看的就是你有没有完整理解约束。空间复杂度和时间复杂度不是加分项是硬性指标。1.2 三份常见答卷错得各有千秋这些年我收集了不少候选人写移动零的初版代码踩坑方式高度集中在三种解法套路典型写法主要问题新数组拼装遍历原数组挑出非零再根据原长度补零复制到新数组空间复杂度O(n)违反“原地”删除后补零循环删除0再在数组尾部追加0删除操作本身是O(n)最坏退化成O(n^2)冒泡式后移遇到0就和后面最近的元素逐位交换方向正确但交换次数多最坏也是O(n^2)这三种写法我都实际见过。第一种最气人因为写起来最短看起来最“对”但完全是空间换时间题目直接不让你用额外数组。第二种常见于用惯了脚本语言的人Python的list、JavaScript的splice都能删元素但数组中间删元素意味着后面所有元素都要左移一堆0的话每删一次都要搬一遍性能惨不忍睹。第三种至少方向对了知道要原地也保持顺序但把“移动0”理解成了“0一点一点往右挪”没有想清楚谁才是“不需要动”的主角。1.3 从失败答卷里提炼出的两个隐含考点看多了这些答案你会发现面试官真正想考的不是“会不会写这道题”而是两个更底层的意识。第一个是空间意识。很多候选人写代码时完全没想过自己申请了多少额外内存。题目说“原地”他第一反应是“我建个新数组不就完了吗”。这背后是脑子里缺少复杂度模型没有把额外空间当成和运行时间一样宝贵的资源。第二个是操作次数意识。题目描述最后那句“尽量减少操作次数”经常被忽略。在工程场景里对一个几百万长度的数组做大量无意义的赋值是实打实的性能损耗。面试里所谓“最优解”通常不是写出来最舒服的版本而是对CPU和内存都友善的版本。这两点才是“简单题”背后的算法思维升级。接下来两节我会从覆盖法和交换法两个角度把这套思维真正落到代码上。2. 覆盖法把“删除零”变成“保留非零”2.1 新数组解法为什么违规原地约束才是灵魂新数组解法写出来大概是这样的def move_zeroes(nums): non_zeros [x for x in nums if x ! 0] for i in range(len(nums)): nums[i] non_zeros[i] if i len(non_zeros) else 0表面上看它最后又把结果写回原数组好像“只是临时借用了一下内存”。但内存峰值是O(n)数据量一大峰值内存直接翻倍甚至更多。原地要求的本质是额外空间O(1)不管你最终有没有把结果写回。为什么原地很重要一个现实原因是数组可能非常大。我处理过模拟项目X里的图像帧数据一帧就是几十MB的浮点数组你要在那块内存上反复做变换再申请一块同样大小的内存内存带宽和缓存压力立刻上来。另一个原因是这常常是更大系统里的一小步后面还要在同一个数组上做其他操作中间插一次大分配对整个流水线都是负担。把“原地”当成硬约束去训练写出代码的工程价值会高出很多。2.2 慢指针的语义一个变量维护一条完整队列覆盖法的设计思路可以这样想既然把0往末尾移动很费劲那不如把所有非零元素“往前压缩”压缩完剩下来的位置天然就是0。整个过程只需要两个指针fast指针负责巡逻每一步向后移动一个位置当fast指向的元素不是0时把它写入nums[slow]然后slow向后移动一位当fast指向的是0时什么都不做继续前进。等fast走完整个数组区间[0, slow)里存的就是所有非零元素而且保持了原有顺序。此时再把从slow到数组末尾的位置全部置0。代码非常短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和fast之间这段区域在覆盖过程中已经变成“语义上的垃圾区”。慢指针不是在删除零而是在保留非零。把fast处的非零值写到slow位置时覆盖掉的是slow处原本的0或者可能是还没处理的数据。等等如果是后者怎么办不会因为slow永远小于等于fast当fast指向非零时slow到fast之间要么是0要么是已经被处理过的位置。被覆盖的位置一定是0这保证了不会有活数据丢。这个思想跟内存池的compact、垃圾回收里的标记-压缩非常像都是“把活对象往前搬一口气清掉尾部”。2.3 操作次数与复杂度的真实账本遍历数组一次赋值次数等于非零元素个数第二轮补零次数等于零元素个数。总体赋值次数加在一起刚好等于数组长度n。时间O(n)空间O(1)。对比一下几种解法的账本解法时间复杂度空间复杂度符合原地保持顺序赋值/交换次数新数组拼装O(n)O(n)否是约2n删除后补零O(n^2)O(1)是是最坏O(n^2)冒泡式后移零O(n^2)O(1)是是最坏O(n^2)覆盖法O(n)O(1)是是n次赋值交换法O(n)O(1)是是最多n次交换覆盖法已经站在最优解门槛上。它唯一的“不完美”在于赋值和置零分成了两轮而且当数组本来没有0时第二轮会白跑一遍。虽然复杂度仍然是O(n)但工程上完全可以在发现数组里没有0的时候直接返回。问题是你怎么知道有没有0可以在第一次遇到0时打一个标记这样全非零数组就能省掉一整轮循环。这个小优化正好引出了交换法能不能一次遍历顺便把零也放到该放的位置根本不补第二轮3. 交换法用“滚动零区间”做无痛搬运3.1 为什么需要交换而不是赋值覆盖法的两个循环可以被合并成一个秘密就在“交换”这两个字上。交换法的指针语义和覆盖法略有不同slow指针在覆盖法里指向“下一个非零元素应该放的位置”在交换法里它同时指向“当前第一个0元素的位置”fast指针依然负责扫描整个数组当nums[fast] ! 0时交换nums[slow]与nums[fast]然后slow。关键点在于从slow到fast之间存在连续的0。第一次交换把非零元素放到slow位置把一个0换到fast位置。这个0会随着fast继续前进被推到越来越靠后的地方形成一段会滚动的“零区间”。每次交换都保证区间[0, slow)内的非零元素顺序不被打乱。代码def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1当fast和slow指向同一个非零元素时交换等于原地自交换没有副作用。当数组里连续好几个非零时slow会一直等于fast代码会做很多次没有意义的自交换。要不要优化掉这个点后面我会专门说这里先记住一个结论交换法用一次遍历同时完成“非零前移”和“零后移”两件事。3.2 循环不变量区间[0, slow)永远是对的面试里能区分高下的不是“能不能写对”而是“能不能说清楚为什么对”。这就要用到循环不变量。交换法在每次循环执行前都维持三条事实区间[0, slow)内所有元素非零并且保持它们在原数组中的相对顺序区间[slow, fast)内所有元素都是0区间[fast, n)是尚未扫描的原始数据。初始化时slow0fast0。区间[0,0)是空区间第一条成立区间[0,0)也是空区间第二条也成立。进入循环后如果nums[fast]0只需要fast这时一个0被并入[slow, fast)区间第二条仍然成立如果nums[fast]!0交换nums[slow]和nums[fast]。由于[slow, fast)全是0交换后slow位置变成这个非零元素fast位置变成0。随后slow、fast三条不变式继续成立。循环结束时fastn因为第二条不变式成立所以[slow, n)全是0因为第一条成立[0, slow)非零且有序。这恰好就是题解。这个证明方法在算法训练里叫“用不变量证明循环正确性”比跑十组用例都管用。你能随口说出这套逻辑面试官基本就不需要再追问边界情况了。很多人讲双指针一上来就是“左指针、右指针”好像双指针只能是相向夹逼。移动零这种快慢指针同向走的题型同样常见。所谓双指针本质上是指针代表两个局部状态一个维护已处理好的部分另一个探索未知区域。理解了这一层比背题目重要得多。3.3 边界测试空数组、全零与连续非零我写完一个数组变换算法习惯固定用五组用例去验证移动零也不例外空数组 []slow和fast都不会越界方法直接返回空数组全零数组 [0, 0, 0]所有元素都不会触发交换结果和原数组一致无零数组 [1, 2, 3, 4]每一次fast都等于slow不断自交换结果是原数组本身单个零在中间 [0, 1, 0, 3, 12]验证非零相对顺序是否保持非零集中在开头 [1, 2, 0, 0, 3, 4]验证零区间滚动的完整过程。跑这些用例不是为了“测试”是为了理解算法语义。比如第3类用例会暴露一个细节完全没有0时交换法仍然会对每个元素做一次自交换。工程上想省掉这些无用操作只需要加一个判断def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: if nums[slow] 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1加了这个条件之后无零数组一次交换都不做零在中间的场景也只在必要时机交换。复杂度不变但代码更贴近“尽量减少操作次数”的要求。3.4 语言差异Python与C的交换细节Python的a, b b, a交换很方便但要注意一个问题当slow和fast指向同一位置时是自交换不会有数据丢失。C里用std::swap对内置类型通常被编译成几条指令逻辑上没有区别。但如果数组元素是自定义结构体std::swap可能设计移动构造和移动赋值成本比简单赋值高不少。如果工程里对象的复制代价很大覆盖法反而更友好因为它第一轮只需要把对象往前搬第二轮只用整数赋值清零不涉及复杂对象的交换void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; } } for (int i slow; i nums.size(); i) { nums[i] 0; } }两种解法没有绝对高下覆盖法在“少写赋值”上更好交换法在“一轮完成”上更漂亮。真正的高手是两种都写过并且知道在什么场景选哪一种。4. 从一道题到一类题稳定分区思维4.1 移动零其实是稳定partition的特例如果你把“非零元素”看成“通过筛选的元素”“零元素”看成“未通过筛选的元素”移动零做的就是在保持筛选后元素相对顺序的前提下把所有通过筛选的元素移到数组前面。算法里有一个专门的名字稳定分区stable partition。快速排序里的partition通常是“基准值左边小、右边大”但那种经典分区用两端交换做是不稳定的会打乱相等元素的原始顺序。移动零的覆盖法和交换法则是稳定分区的一种具体实现慢指针维护已分区区间的尾部快指针扫描未分区区间遇到满足条件的元素就把它“追加”到已分区区间末尾。一旦你建立起这种抽象马上就会发现移动零不是在“处理一个奇怪的数组”而是在“实现一个具有稳定性的谓词分区函数”。这个模板可以解决一大串变体题。4.2 荷兰国旗问题从两分区到三分区荷兰国旗问题给一个只含0、1、2三种元素的数组要求原地排序成 [0...0, 1...1, 2...2]。常规解法是三指针左指针维护0区右指针维护2区扫描指针遍历中间。本质上就是从“两分区”升维到“三分区”。理解了移动零是稳定partition后荷兰国旗就相当于“在同一个数组上做两次分区”第一次把0和非0分开第二次在非0区间把1和2分开。当然直接三指针一次遍历更省但分区视角能让解法变得更好理解。C三指针版本void sortColors(vectorint nums) { int p0 0, p2 nums.size() - 1, i 0; while (i p2) { if (nums[i] 0) { swap(nums[p0], nums[i]); } else if (nums[i] 2) { swap(nums[p2--], nums[i]); // 交换来的未知元素需要重新检查 } else { i; } } }注意最后一行注释里的细节当把2交换回去时i不能前进因为nums[p2]原来的值可能是0、可能还是2都得重新处理。这个边界是面试高频追问点也是很多候选人写错的地方。4.3 变体题串讲移除指定值、奇偶分离、正负分隔移动零的模板能直接套到这些题上“移除元素”给定一个值val把数组里所有不等于val的元素放到前面。判断条件从“非零”改成“不等于val”返回slow作为新长度末尾不必清空奇偶分离把偶数放前面、奇数放后面要求保持相对顺序时用同向慢指针不要求顺序时用两端交换更快正负分隔把大于等于0和小于0分成两段原理相同把某种特定元素移动到数组首部或尾部只是把判断条件从“等于target”改成“不等于target”字符串里的连续空格压缩slow记录有效字符位置fast扫描也能看到同样的影子。我举一个最简单的例子。移除元素的代码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”以及省掉了末尾清零。这两题如果放在一起学效率极高因为指针语义完全复用。4.4 稳定分区在工程里的影子稳定分区不只是在面试题里转圈。做数据库索引整理时要把有效记录和失效记录分离同时保持主键顺序很多压缩和迁移逻辑就是这种稳定分区。做视频帧批处理时要过滤掉坏帧又保留时间顺序用的也是同向双指针。内存分配器整理碎片时要搬移对象搬移过程中必须维护对象之间的相对关系这也是稳定分区。可以说稳定分区是一种“在有限空间里有序整理数据”的通用操作。一道简单题能练出这样的抽象能力是它最大的价值。很多程序员刷了几百道题遇到新题还是不会就是因为只记解法不做抽象。移动零恰恰是性价比最高的抽象入口。5. 把“简单题”的价值榨干面试呈现与学习路径5.1 面试时怎么讲这道题才能体现思维升级如果只是写出答案这道题在面试官那里只能拿到及格分。真正的加分项是从头到尾讲清思路顺序大概是先口头确认约束原地、保持相对顺序、尽量减少操作次数三个约束分别对应什么解法主动淘汰错误方案说明新数组为什么不行、删除法为什么复杂度差从覆盖法讲到交换法同时解释慢指针语义和循环不变量用一组边界用例手动走一遍顺嘴提一句变体这是稳定partition的特例荷兰国旗、移除元素都可以复用。我见过不少候选人键盘敲得飞起代码全对但被问“为什么这样写是对的”就卡住。算法面试真正想考察的不是“能不能运行通过”而是“遇到约束条件时能不能把直觉翻译成严谨逻辑”。移动零就是最好的试金石。你在讲这道题时能主动说出“循环不变量”这个词就已经和只背答案的选手拉开差距了。5.2 边界用例清单与复杂度自查模板我整理了一个极简的自查模板适用于绝大多数数组原地变换题输入是空数组吗数组里全是目标值或全不是目标值目标值集中在开头、结尾还是连续多个数组长度是奇数还是偶数循环过程中指针会不会越界如果从一维扩展到二维这个思路还成立吗复杂度自查问自己三件事每个元素最多被访问几次额外空间是常数还是和数据规模有关操作次数能不能在常数次遍历内完成移动零的两种解法都能回答每个元素访问常数次额外空间O(1)一到两轮遍历。如果你的解法里出现了排序、嵌套循环、重建数组就要停下来想一想有没有更优的结构。5.3 这道题练完下一个该啃什么移动零是一个“锚点题目”掌握了它可以顺藤摸瓜去啃这些内容合并两个有序数组同样用指针但要从尾部向前走避免覆盖未处理数据删除有序数组中的重复项用“保留区间的最后一个元素”做比较本质上还是快慢指针维护有效区间快速排序的partition实现理解为什么经典版本不稳定以及什么时候可以用不稳定版本荷兰国旗问题学习三分区指针的边界处理容器盛水、最长连续序列这类题双指针的使用场景从“同步扫描”扩展到“夹逼游标”。我自己带新人时通常把移动零作为双指针训练的第一课。因为它代码量小适合逐行推敲又能引出循环不变量、复杂度分析、稳定分区三层递进。很多人做完这道题只记住一个结论“用快慢指针”没记住“为什么快慢指针能交换”。这样就把一道好题浪费了。最后分享一个我实际用的小技巧刷这类数组题时不要急着在编辑框里写整段代码先在纸上画出数组和两个指针的位置手动模拟两三步。移动零这道题更是如此你只要在纸上画一次零区间滚动就再也不会忘了它为什么能保持顺序、为什么一轮交换就能收工。很多正确答案不是敲出来的是在纸上试出来的。 
长河君 · 2026/10/22 19:51:04 · 阅读 1.2k 解析移动零：双指针与原地算法背后的思维升级
最近一次模拟面试里我让候选人A写那道某在线题库里的经典题“移动零”。题目描述不长给定一个数组把所有的0移动到数组末尾同时保持非零元素的相对顺序要求在不复制数组的前提下原地完成。A同学三十秒交出答案遍历原数组把非零元素挑出来再在结尾补上若干个0。我追问了一句“那你申请的新数组放在哪了”他盯着屏幕愣是三分钟没动手。这道题在题库里标的难度是“简单”但在我这些年参与技术评审和带新人的经历里它恰恰是最容易翻车的一道。不是候选人不会写而是很多人把它当成了“删除零元素再补零”的字符串题完全没意识到题目里那句“原地”才是真正要考的东西。这篇文章我想把这道题掰开揉碎讲讲从直觉解法到最优解法的思维升级过程。它背后藏着一种在整个算法训练里都极其重要的能力把模糊的需求翻译成精确的指针语义。1. 一道“送分题”怎么成了面试翻车重灾区1.1 题目本身有多简单先把需求拆干净给定一个数组 nums例如 [0, 1, 0, 3, 12]要求输出 [1, 3, 12, 0, 0]。就这么点事。但题目里其实藏着三个隐性约束少看一个解法就会变味不复制数组原地操作只能在这一个数组的内存空间里做文章非零元素的相对顺序不能变1 必须在 3 前面3 必须在 12 前面尽量减少操作次数不是“能跑就行”而是要在时间复杂度和赋值成本上都有交代。“保持相对顺序”这条最容易被轻视。我见过有人一看到移动零马上想到左右双指针左指针找0右指针找非零然后交换。这个思路用在快速排序的partition上没问题但用在这里会出事。比如数组 [1, 0, 0, 2]左边指针指向下标1的0右边指针从末尾找到下标3的2交换后变成 [1, 2, 0, 0]看似正确但再来一个例子 [0, 0, 1, 2]左边找到下标0的0右边找到下标2的1交换后变成 [1, 0, 0, 2]非零元素1跑到2前面去了相对顺序被破坏。这就是“简单题”的陷阱。需求有三个约束缺一个看起来也能跑但面试官看的就是你有没有完整理解约束。空间复杂度和时间复杂度不是加分项是硬性指标。1.2 三份常见答卷错得各有千秋这些年我收集了不少候选人写移动零的初版代码踩坑方式高度集中在三种解法套路典型写法主要问题新数组拼装遍历原数组挑出非零再根据原长度补零复制到新数组空间复杂度O(n)违反“原地”删除后补零循环删除0再在数组尾部追加0删除操作本身是O(n)最坏退化成O(n^2)冒泡式后移遇到0就和后面最近的元素逐位交换方向正确但交换次数多最坏也是O(n^2)这三种写法我都实际见过。第一种最气人因为写起来最短看起来最“对”但完全是空间换时间题目直接不让你用额外数组。第二种常见于用惯了脚本语言的人Python的list、JavaScript的splice都能删元素但数组中间删元素意味着后面所有元素都要左移一堆0的话每删一次都要搬一遍性能惨不忍睹。第三种至少方向对了知道要原地也保持顺序但把“移动0”理解成了“0一点一点往右挪”没有想清楚谁才是“不需要动”的主角。1.3 从失败答卷里提炼出的两个隐含考点看多了这些答案你会发现面试官真正想考的不是“会不会写这道题”而是两个更底层的意识。第一个是空间意识。很多候选人写代码时完全没想过自己申请了多少额外内存。题目说“原地”他第一反应是“我建个新数组不就完了吗”。这背后是脑子里缺少复杂度模型没有把额外空间当成和运行时间一样宝贵的资源。第二个是操作次数意识。题目描述最后那句“尽量减少操作次数”经常被忽略。在工程场景里对一个几百万长度的数组做大量无意义的赋值是实打实的性能损耗。面试里所谓“最优解”通常不是写出来最舒服的版本而是对CPU和内存都友善的版本。这两点才是“简单题”背后的算法思维升级。接下来两节我会从覆盖法和交换法两个角度把这套思维真正落到代码上。2. 覆盖法把“删除零”变成“保留非零”2.1 新数组解法为什么违规原地约束才是灵魂新数组解法写出来大概是这样的def move_zeroes(nums): non_zeros [x for x in nums if x ! 0] for i in range(len(nums)): nums[i] non_zeros[i] if i len(non_zeros) else 0表面上看它最后又把结果写回原数组好像“只是临时借用了一下内存”。但内存峰值是O(n)数据量一大峰值内存直接翻倍甚至更多。原地要求的本质是额外空间O(1)不管你最终有没有把结果写回。为什么原地很重要一个现实原因是数组可能非常大。我处理过模拟项目X里的图像帧数据一帧就是几十MB的浮点数组你要在那块内存上反复做变换再申请一块同样大小的内存内存带宽和缓存压力立刻上来。另一个原因是这常常是更大系统里的一小步后面还要在同一个数组上做其他操作中间插一次大分配对整个流水线都是负担。把“原地”当成硬约束去训练写出代码的工程价值会高出很多。2.2 慢指针的语义一个变量维护一条完整队列覆盖法的设计思路可以这样想既然把0往末尾移动很费劲那不如把所有非零元素“往前压缩”压缩完剩下来的位置天然就是0。整个过程只需要两个指针fast指针负责巡逻每一步向后移动一个位置当fast指向的元素不是0时把它写入nums[slow]然后slow向后移动一位当fast指向的是0时什么都不做继续前进。等fast走完整个数组区间[0, slow)里存的就是所有非零元素而且保持了原有顺序。此时再把从slow到数组末尾的位置全部置0。代码非常短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和fast之间这段区域在覆盖过程中已经变成“语义上的垃圾区”。慢指针不是在删除零而是在保留非零。把fast处的非零值写到slow位置时覆盖掉的是slow处原本的0或者可能是还没处理的数据。等等如果是后者怎么办不会因为slow永远小于等于fast当fast指向非零时slow到fast之间要么是0要么是已经被处理过的位置。被覆盖的位置一定是0这保证了不会有活数据丢。这个思想跟内存池的compact、垃圾回收里的标记-压缩非常像都是“把活对象往前搬一口气清掉尾部”。2.3 操作次数与复杂度的真实账本遍历数组一次赋值次数等于非零元素个数第二轮补零次数等于零元素个数。总体赋值次数加在一起刚好等于数组长度n。时间O(n)空间O(1)。对比一下几种解法的账本解法时间复杂度空间复杂度符合原地保持顺序赋值/交换次数新数组拼装O(n)O(n)否是约2n删除后补零O(n^2)O(1)是是最坏O(n^2)冒泡式后移零O(n^2)O(1)是是最坏O(n^2)覆盖法O(n)O(1)是是n次赋值交换法O(n)O(1)是是最多n次交换覆盖法已经站在最优解门槛上。它唯一的“不完美”在于赋值和置零分成了两轮而且当数组本来没有0时第二轮会白跑一遍。虽然复杂度仍然是O(n)但工程上完全可以在发现数组里没有0的时候直接返回。问题是你怎么知道有没有0可以在第一次遇到0时打一个标记这样全非零数组就能省掉一整轮循环。这个小优化正好引出了交换法能不能一次遍历顺便把零也放到该放的位置根本不补第二轮3. 交换法用“滚动零区间”做无痛搬运3.1 为什么需要交换而不是赋值覆盖法的两个循环可以被合并成一个秘密就在“交换”这两个字上。交换法的指针语义和覆盖法略有不同slow指针在覆盖法里指向“下一个非零元素应该放的位置”在交换法里它同时指向“当前第一个0元素的位置”fast指针依然负责扫描整个数组当nums[fast] ! 0时交换nums[slow]与nums[fast]然后slow。关键点在于从slow到fast之间存在连续的0。第一次交换把非零元素放到slow位置把一个0换到fast位置。这个0会随着fast继续前进被推到越来越靠后的地方形成一段会滚动的“零区间”。每次交换都保证区间[0, slow)内的非零元素顺序不被打乱。代码def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1当fast和slow指向同一个非零元素时交换等于原地自交换没有副作用。当数组里连续好几个非零时slow会一直等于fast代码会做很多次没有意义的自交换。要不要优化掉这个点后面我会专门说这里先记住一个结论交换法用一次遍历同时完成“非零前移”和“零后移”两件事。3.2 循环不变量区间[0, slow)永远是对的面试里能区分高下的不是“能不能写对”而是“能不能说清楚为什么对”。这就要用到循环不变量。交换法在每次循环执行前都维持三条事实区间[0, slow)内所有元素非零并且保持它们在原数组中的相对顺序区间[slow, fast)内所有元素都是0区间[fast, n)是尚未扫描的原始数据。初始化时slow0fast0。区间[0,0)是空区间第一条成立区间[0,0)也是空区间第二条也成立。进入循环后如果nums[fast]0只需要fast这时一个0被并入[slow, fast)区间第二条仍然成立如果nums[fast]!0交换nums[slow]和nums[fast]。由于[slow, fast)全是0交换后slow位置变成这个非零元素fast位置变成0。随后slow、fast三条不变式继续成立。循环结束时fastn因为第二条不变式成立所以[slow, n)全是0因为第一条成立[0, slow)非零且有序。这恰好就是题解。这个证明方法在算法训练里叫“用不变量证明循环正确性”比跑十组用例都管用。你能随口说出这套逻辑面试官基本就不需要再追问边界情况了。很多人讲双指针一上来就是“左指针、右指针”好像双指针只能是相向夹逼。移动零这种快慢指针同向走的题型同样常见。所谓双指针本质上是指针代表两个局部状态一个维护已处理好的部分另一个探索未知区域。理解了这一层比背题目重要得多。3.3 边界测试空数组、全零与连续非零我写完一个数组变换算法习惯固定用五组用例去验证移动零也不例外空数组 []slow和fast都不会越界方法直接返回空数组全零数组 [0, 0, 0]所有元素都不会触发交换结果和原数组一致无零数组 [1, 2, 3, 4]每一次fast都等于slow不断自交换结果是原数组本身单个零在中间 [0, 1, 0, 3, 12]验证非零相对顺序是否保持非零集中在开头 [1, 2, 0, 0, 3, 4]验证零区间滚动的完整过程。跑这些用例不是为了“测试”是为了理解算法语义。比如第3类用例会暴露一个细节完全没有0时交换法仍然会对每个元素做一次自交换。工程上想省掉这些无用操作只需要加一个判断def move_zeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: if nums[slow] 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1加了这个条件之后无零数组一次交换都不做零在中间的场景也只在必要时机交换。复杂度不变但代码更贴近“尽量减少操作次数”的要求。3.4 语言差异Python与C的交换细节Python的a, b b, a交换很方便但要注意一个问题当slow和fast指向同一位置时是自交换不会有数据丢失。C里用std::swap对内置类型通常被编译成几条指令逻辑上没有区别。但如果数组元素是自定义结构体std::swap可能设计移动构造和移动赋值成本比简单赋值高不少。如果工程里对象的复制代价很大覆盖法反而更友好因为它第一轮只需要把对象往前搬第二轮只用整数赋值清零不涉及复杂对象的交换void moveZeroes(vectorint nums) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; } } for (int i slow; i nums.size(); i) { nums[i] 0; } }两种解法没有绝对高下覆盖法在“少写赋值”上更好交换法在“一轮完成”上更漂亮。真正的高手是两种都写过并且知道在什么场景选哪一种。4. 从一道题到一类题稳定分区思维4.1 移动零其实是稳定partition的特例如果你把“非零元素”看成“通过筛选的元素”“零元素”看成“未通过筛选的元素”移动零做的就是在保持筛选后元素相对顺序的前提下把所有通过筛选的元素移到数组前面。算法里有一个专门的名字稳定分区stable partition。快速排序里的partition通常是“基准值左边小、右边大”但那种经典分区用两端交换做是不稳定的会打乱相等元素的原始顺序。移动零的覆盖法和交换法则是稳定分区的一种具体实现慢指针维护已分区区间的尾部快指针扫描未分区区间遇到满足条件的元素就把它“追加”到已分区区间末尾。一旦你建立起这种抽象马上就会发现移动零不是在“处理一个奇怪的数组”而是在“实现一个具有稳定性的谓词分区函数”。这个模板可以解决一大串变体题。4.2 荷兰国旗问题从两分区到三分区荷兰国旗问题给一个只含0、1、2三种元素的数组要求原地排序成 [0...0, 1...1, 2...2]。常规解法是三指针左指针维护0区右指针维护2区扫描指针遍历中间。本质上就是从“两分区”升维到“三分区”。理解了移动零是稳定partition后荷兰国旗就相当于“在同一个数组上做两次分区”第一次把0和非0分开第二次在非0区间把1和2分开。当然直接三指针一次遍历更省但分区视角能让解法变得更好理解。C三指针版本void sortColors(vectorint nums) { int p0 0, p2 nums.size() - 1, i 0; while (i p2) { if (nums[i] 0) { swap(nums[p0], nums[i]); } else if (nums[i] 2) { swap(nums[p2--], nums[i]); // 交换来的未知元素需要重新检查 } else { i; } } }注意最后一行注释里的细节当把2交换回去时i不能前进因为nums[p2]原来的值可能是0、可能还是2都得重新处理。这个边界是面试高频追问点也是很多候选人写错的地方。4.3 变体题串讲移除指定值、奇偶分离、正负分隔移动零的模板能直接套到这些题上“移除元素”给定一个值val把数组里所有不等于val的元素放到前面。判断条件从“非零”改成“不等于val”返回slow作为新长度末尾不必清空奇偶分离把偶数放前面、奇数放后面要求保持相对顺序时用同向慢指针不要求顺序时用两端交换更快正负分隔把大于等于0和小于0分成两段原理相同把某种特定元素移动到数组首部或尾部只是把判断条件从“等于target”改成“不等于target”字符串里的连续空格压缩slow记录有效字符位置fast扫描也能看到同样的影子。我举一个最简单的例子。移除元素的代码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”以及省掉了末尾清零。这两题如果放在一起学效率极高因为指针语义完全复用。4.4 稳定分区在工程里的影子稳定分区不只是在面试题里转圈。做数据库索引整理时要把有效记录和失效记录分离同时保持主键顺序很多压缩和迁移逻辑就是这种稳定分区。做视频帧批处理时要过滤掉坏帧又保留时间顺序用的也是同向双指针。内存分配器整理碎片时要搬移对象搬移过程中必须维护对象之间的相对关系这也是稳定分区。可以说稳定分区是一种“在有限空间里有序整理数据”的通用操作。一道简单题能练出这样的抽象能力是它最大的价值。很多程序员刷了几百道题遇到新题还是不会就是因为只记解法不做抽象。移动零恰恰是性价比最高的抽象入口。5. 把“简单题”的价值榨干面试呈现与学习路径5.1 面试时怎么讲这道题才能体现思维升级如果只是写出答案这道题在面试官那里只能拿到及格分。真正的加分项是从头到尾讲清思路顺序大概是先口头确认约束原地、保持相对顺序、尽量减少操作次数三个约束分别对应什么解法主动淘汰错误方案说明新数组为什么不行、删除法为什么复杂度差从覆盖法讲到交换法同时解释慢指针语义和循环不变量用一组边界用例手动走一遍顺嘴提一句变体这是稳定partition的特例荷兰国旗、移除元素都可以复用。我见过不少候选人键盘敲得飞起代码全对但被问“为什么这样写是对的”就卡住。算法面试真正想考察的不是“能不能运行通过”而是“遇到约束条件时能不能把直觉翻译成严谨逻辑”。移动零就是最好的试金石。你在讲这道题时能主动说出“循环不变量”这个词就已经和只背答案的选手拉开差距了。5.2 边界用例清单与复杂度自查模板我整理了一个极简的自查模板适用于绝大多数数组原地变换题输入是空数组吗数组里全是目标值或全不是目标值目标值集中在开头、结尾还是连续多个数组长度是奇数还是偶数循环过程中指针会不会越界如果从一维扩展到二维这个思路还成立吗复杂度自查问自己三件事每个元素最多被访问几次额外空间是常数还是和数据规模有关操作次数能不能在常数次遍历内完成移动零的两种解法都能回答每个元素访问常数次额外空间O(1)一到两轮遍历。如果你的解法里出现了排序、嵌套循环、重建数组就要停下来想一想有没有更优的结构。5.3 这道题练完下一个该啃什么移动零是一个“锚点题目”掌握了它可以顺藤摸瓜去啃这些内容合并两个有序数组同样用指针但要从尾部向前走避免覆盖未处理数据删除有序数组中的重复项用“保留区间的最后一个元素”做比较本质上还是快慢指针维护有效区间快速排序的partition实现理解为什么经典版本不稳定以及什么时候可以用不稳定版本荷兰国旗问题学习三分区指针的边界处理容器盛水、最长连续序列这类题双指针的使用场景从“同步扫描”扩展到“夹逼游标”。我自己带新人时通常把移动零作为双指针训练的第一课。因为它代码量小适合逐行推敲又能引出循环不变量、复杂度分析、稳定分区三层递进。很多人做完这道题只记住一个结论“用快慢指针”没记住“为什么快慢指针能交换”。这样就把一道好题浪费了。最后分享一个我实际用的小技巧刷这类数组题时不要急着在编辑框里写整段代码先在纸上画出数组和两个指针的位置手动模拟两三步。移动零这道题更是如此你只要在纸上画一次零区间滚动就再也不会忘了它为什么能保持顺序、为什么一轮交换就能收工。很多正确答案不是敲出来的是在纸上试出来的。