移动零双指针解法：原地操作与相对顺序的工程思维

某在线判题系统的题库里有一道编号283的题目名叫“移动零”。难度标的是“简单”但我见过不少人在面试环节被它问住。题目本身一句话就能讲清给你一个整数数组把所有的0移动到数组末尾同时保持非零元素的相对顺序并且必须在原数组上操作不能拷贝一份新的数组。很多刚刷题的人看到这道题第一反应是遍历一遍遇到0就删掉再在末尾补0不就行了可一旦把这句话落到代码里问题就来了——数组的删除操作并不便宜而“不能拷贝新数组”直接堵死了“另开一个数组”的偷懒方案。这篇文章就针对这道题从题目意图、暴力解、双指针推演、实现细节、边界测试一直讲到同类型题目的扩展。代码以Java为主但思路可以平移到Python、C、Go等任何语言。1. 理解“移动零”到底在考什么题目里的三个关键词1.1 一个数组操作题为什么要强调“顺序”很多人以为移动零就是“把0往最后放”于是第一版往往写成“先统计非零元素再填回数组”。这样确实能保证所有0都在末尾但如果题目没有额外规定你可以随意打乱非零元素的顺序比如输入[0,1,0,3,12]你可以输出[12,3,1,0,0]。题目真正要求的是“保持非零元素的相对顺序”也就是输出必须是[1,3,12,0,0]。这个约束直接决定了我们不能对数组做整体重新排序只能做线性扫描和局部的搬移。换句话说这题不是“分类汇总”而是“保序移动”。我见过有人一上来就尝试把非零元素按值排序或者原地把整个数组重排成“非零在前、零在后”。从结果看似乎满足了“0在末尾”但非零元素的相对顺序被破坏了。这类错误在面试中非常致命因为面试官一眼就能看出你根本没有读懂题目里的“保持相对顺序”这几个字。所谓相对顺序可以理解为队伍里原本排在前面的那个人移动后仍然站在另一个人的前面没人能插队。这种约束在工程场景里很重要比如数据库里某些字段的顺序隐含业务语义不能随便打乱。1.2 原地操作和空间复杂度的关系“原地”两个字的含义是空间复杂度O(1)除了传入的数组本身你只能使用常数级别的临时变量。很多新手第一版代码会这样写public void moveZeroes(int[] nums) { int[] help new int[nums.length]; // 把非零元素放到help里再拷回nums ... }从逻辑上看这个方案完全可行时间复杂度也是O(n)但它使用了一个大小为n的额外数组空间复杂度O(n)不符合题意。如果你在面试里写出这种代码面试官通常不会直接说你错而是追问一句能不能不用额外空间这时你如果只会“另开数组”的解法就暴露了理解深度不够。要真正理解“原地”你可以把数组想象成一块白板你只能在这块白板上擦掉某个格子里的值、再写上新的值但不能拿另一块更大的白板来辅助。函数签名是void moveZeroes(int[] nums)返回值是空这本身就是一种暗示题目希望直接修改原数组而不是返回一个新数组。C里的vectorint nums、Python里的nums可变对象也都是同样的意图。1.3 题目真正限定的约束是“移动”不是“排序”把0和非0分开本质上等价于一种“稳定二分”把非零元素稳定地放在前面把零元素稳定地放在后面。在排序领域“稳定性”指的是相等元素在排序前后保持原有相对顺序。那这里非零元素之间相对顺序不变就是稳定性在数组分类操作中的体现。我常给人打一个比方排队买东西队伍里混着几个“不看价格直接走”的人把这些人清理出去剩下的人必须保持原来的先后顺序。你不能为了方便把后面的人拽到前面来插队。这道题里的0就是那些“被清理的人”只不过他们不能真的被清走而是要去排队尾。把0想象成一个特殊值后你会发现问题的本质是“把某一类元素移动到区间末端”。这种抽象能力非常值钱。以后你遇到“把偶数移到前面并保持相对顺序”“把某个指定颜色移到前面”等题型时核心思路可以完全复用。所以移动零不只是一个小题它是一整个“保序分类”系列的入门代表。2. 暴力解法为什么会被面试官打回从删除元素思维到复杂度陷阱2.1 最直观的“数零法”为什么看起来没毛病先看一个很多初学者都能想到的版本public void moveZeroes(int[] nums) { ListInteger list new ArrayList(); for (int n : nums) { if (n ! 0) list.add(n); } for (int i 0; i list.size(); i) { nums[i] list.get(i); } for (int i list.size(); i nums.length; i) { nums[i] 0; } }这个逻辑清晰测试用例也能过。可一旦面试官追问它的第一个问题就是额外空间我们使用了一个ArrayList来暂存非零元素空间复杂度是O(n)。如果输入数组特别大比如几百万个元素这个列表会占掉大量内存。第二个问题也是更容易被忽略的它不符合“原地”要求。不过你也不要把“数零法”贬得一文不值。它在设计上体现了一个非常重要的思想先把非零元素拎出来再统一补零。后面要讲的覆盖法本质上就是把这个思想改造成原地版本。面试官其实很乐意看到你从这个版本起步然后自己说出“这里用了额外空间我能不能去掉它”这样的话这本身就是一种加分表现。2.2 数组删除为什么贵ArrayList.remove的幻觉有人会想那我遇到0就删除再在末尾加0这不就是原地操作吗在Java里用ArrayList的remove确实能写出来但性能非常糟糕。数组是连续存储结构删除中间某个元素需要把后面所有元素往前搬一格。单次删除操作就是O(n)如果数组里有k个0最坏情况下总体复杂度会到O(n*k)也就是O(n^2)。比如一个数组接近全是0你打算把0一个个删掉再一个个补回去那意味着大量元素被反复搬动数据量稍大就会严重超时。C里的vector::erase、Java里的ArrayList.remove底层本质都一样把后续元素逐个前移。这个操作的语言实现再优化也绕不开“连续内存搬移”的数据结构特性。所以只要是“数组原地操作”第一反应不应该是删除而应该是“覆盖或交换”。实际工程中如果一个系统里频繁删除数组中间元素通常也该考虑换成链表结构而不是硬扛。2.3 标记后移动另一种看起来很聪明的写法还有一种经常出现的“聪明”写法先扫描一遍数出0的个数然后从后往前把非零元素往后搬。例如有人会遍历到0时把后面的元素整体前移最后再补0。这个思路能保证相对顺序但仍然是O(n^2)因为它反复搬运了大量元素。给你一个简易的“复杂度心跳测试”方法把数组长度翻倍看运行时间大约变几倍。如果时间基本翻倍说明是O(n)如果时间翻了4倍大概率是O(n^2)。用一个长度为十万和二十万的随机数组实测O(n^2)的代码在二十万规模时往往已经卡到数百毫秒甚至秒级而O(n)的解法依然是微秒级线性增长。这就是这道题为什么一定要追求线性复杂度。另外还要提醒一句不要一来就写“从后往前”。这题要求把0移到末尾如果从后往前处理很容易把非零元素原本的覆盖顺序搞混。等你想清楚的时候别人双指针已经写完了。遇到数组分类移动题先默认从左往右扫描通过两个指针控制位置是错误的概率最低的路径。3. 双指针到底在指向什么一张草稿纸推演整个过程3.1 慢指针的定义下一个非零元素该放的位置定义left表示“已经整理好的非零元素区的下一个空位”初始为0。它的含义是扫到当前为止前面left个位置已经存放了正确顺序的非零元素。当right发现一个非零元素时就把它放到left这个位置然后left加1。你可以把它理解为“队伍的前端口袋”left永远指向队伍尾巴等待新成员加入。如果当前元素是0说明它不应该在这个队伍里left不动如果当前元素非零就把它塞进队伍末尾然后队伍长度加1。很多人双指针写失败是因为没有先定义清楚指针含义只是在循环里跟着感觉走。面试官问到“left到底指向什么”时如果你回答不出来基本上就凉了。相反如果你能脱口而出“left是下一个非零元素应该放置的下标”面试官会立刻觉得你思路清晰。3.2 快指针的工作方式扫描每一个元素定义right为扫描指针每次循环右移一位。right负责判断当前元素是不是0。如果是0跳过如果不是0就说明它是我们需要的元素要与left位置交换。这里有一个关键点right始终走在left前面所以left位置的原始数据要么是0要么已经被right扫描过。交换时不会丢失任何还没处理过的信息。这个“安全性”是双指针算法正确性的基础。你可以想象成两个人一起整理房间left是整理好的区域的边界right是探索新区域的脚步。right每看到一个不是0的物件就交给left放进整理好的区域里看到0就先放着不动。当right走到房间尽头时整个房间的0自然都堆到了后段非零物件都整齐排列在前段。整个过程每个物件最多被碰一次效率很高。3.3 手推一个例子0 1 0 3 12我们用最经典的输入[0,1,0,3,12]走一遍。初始left0right0。right0nums[0]0跳过left保持0 right1nums[1]1非零交换nums[0]和nums[1]数组变为[1,0,0,3,12]left1 right2nums[2]0跳过left保持1 right3nums[3]3非零交换nums[1]和nums[3]数组变为[1,3,0,0,12]left2 right4nums[4]12非零交换nums[2]和nums[4]数组变为[1,3,12,0,0]left3可以看到每个非零元素都被依次推到前面而0被留在了后面。非零元素之间的先后顺序没有改变因为每次交换都是把“第一个未整理位置”上的0和非零元素互换非零元素不会跨过另一个非零元素。这就是“稳定”的来源。你可以再换一个输入验证[1,0,0,2]。right0时遇到1left已经指向0但leftright交换自已完成right1、2时连续遇到两个0都跳过right3遇到2left1交换nums[1]和nums[3]数组变成[1,2,0,0]。这个例子告诉我们连续的0会通过一次交换被整体“抛”到后面不需要对每个0单独处理。3.4 两个指针的距离里藏着什么left和right之间的距离其实等于“在right已经扫描过的范围内遇到过的0的个数”。如果left和right离得很远说明中间隔了很多个0如果两者始终相等说明到目前为止还没有出现0。这个距离常数在分析算法时常被提到每次非零交换后这个距离不变因为它只是把0从左侧换到了右侧。真正在工作的是right的推进left则在有非零时追一步。理解了这层关系你就能自如应对面试官的各种追问比如“零特别少时你的算法会做多余的事吗”——会所以在代码里可以用if (left ! right)避免自交换这就是第4节要讲的实现细节。4. 三种代码写法与运行细节交换、覆盖、二次扫描的取舍4.1 写法A快慢指针交换法最推荐这是最经典也最推荐在面试中写出的版本public void moveZeroes(int[] nums) { int left 0; for (int right 0; right nums.length; right) { if (nums[right] ! 0) { if (left ! right) { int tmp nums[left]; nums[left] nums[right]; nums[right] tmp; } left; } } }这里加了一个if (left ! right)的判断作用在于当数组本身已经处于“非零元素靠前、零靠后”的状态时比如[1,2,3]right和left同步前进交换自己毫无意义还凭空多了三次赋值。加上判断后这类情况可以完全避免无效操作。如果你担心加判断会让代码变得不够直观可以先写不带判断的版本再在写完后主动说一句“这里可以优化一下如果left和right相等交换没有意义我可以加一个判断避免它。”面试官通常会对这个细节眼前一亮。4.2 写法B覆盖后补零代码最短public void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { nums[slow] nums[fast]; } } while (slow nums.length) { nums[slow] 0; } }这个写法思路非常清晰第一趟把非零元素按顺序往前覆盖记录非零元素的个数第二趟从slow位置开始补0。相比交换法它少了一个临时变量的操作代价是要多一个“最后补零”的过程。它的一个缺点是当非零元素占比很高且原本就排得比较整齐时会产生大量“自己覆盖自己”的赋值。比如[1,2,3,4,5]它会每个元素都赋一遍自己然后发现slow已经到末尾不需要补0。从常数因子来看它并不比交换法更有优势。但如果你更看重“半小时内写对”这个版本反而最不容易出错。4.3 写法C二次扫描先数零再搬运public void moveZeroes(int[] nums) { int n nums.length; int count 0; for (int num : nums) { if (num ! 0) count; } int pos 0; for (int num : nums) { if (num ! 0) { nums[pos] num; } } for (int i pos; i n; i) { nums[i] 0; } }这个写法与写法B没有本质区别只是先把非零数量算出来方便后续补零时知道要补多少。它读起来特别“说人话”第一步统计第二步搬运第三步补零。如果真实面试里第一轮想快速给一个能跑的版本这种写法最容易讲清楚。每个步骤都很直白不需要解释指针的微妙含义。但它的缺点是必须扫描两到三遍常数操作更多。面试官如果继续问“能不能只扫一遍”你可以自然过渡到交换法这反而成了一个展现你分析能力的契机。4.4 三种写法的性能对比写法思路额外空间最坏赋值情况适合场景交换法遇非零就与left交换O(1)约3n次赋值每次交换3步零较多时更高效面试最稳覆盖后补零非零前移末尾补零O(1)约2n次赋值代码最短适合快速框架二次扫描先统计再搬运O(1)约2n次赋值思路直观讲解友好严格来说交换法每个交换需要一次临时变量操作实际是3次赋值覆盖法和补零法每个位置通常是一次赋值。所以“交换法一定更快”是个错觉。当数组里零非常少且非零元素本就在正确位置时覆盖法反而更快因为它不需要交换。但在零分布较多或零分布不均匀时交换法更少移动元素。这道题最常被忽略的其实是“尽量减少操作次数”这句话。如果你的代码里有多余的自我赋值在性能测试里可能只是慢一点点但面试官一旦看穿会觉得你对常数因子不够敏感。加一行if (left ! right)就是最简单的敏感性体现。4.5 面试时怎么写更稳我的建议是先写覆盖后补零版本保证逻辑正确然后主动说“我可以优化成交换法减少无效赋值”再把代码过渡到交换法。这样面试官能看到你从“能跑”到“跑得好”的完整思路而不是一上来就背一个标准解。另外写代码时一定把两个指针的注释写清楚。比如// left下一个非零元素应该放的位置 // right扫描指针从左往右找非零元素这行注释成本极低但能极大拉高面试官对你的评价。它证明你不是在背题而是真的知道指针在干什么。5. 这道题真正的边界弹药库从全零到负数的测试清单5.1 空数组和长度1空数组for循环不进入程序直接结束没有副作用。长度为1时如果元素是0则不做处理如果元素非0left与right同步加1也不会出错。这里有一个隐藏考点函数签名通常不允许传入null但如果你在极端情况下遇到null直接判空返回是稳妥做法。不过力扣风格的特点是空数组也算合法输入所以至少你的代码不能对空数组抛异常。我在实际写的时候习惯在方法开头不加额外判断因为for循环天然安全。但如果你用foreach遍历尤其是涉及索引的时候要小心空数组不会造成ArrayIndexOutOfBoundsException别把简单题写出边界错误。5.2 全部是0和全部非0全0场景比如[0,0,0]right一路走nums[right] ! 0始终不成立left始终为0所有元素原地不动结果还是[0,0,0]。看起来没做什么但这是正确结果。全非0场景比如[1,2,3]right每步递增left也每步递增由于加了if (left ! right)数组完全不变。这其实是最理想的情况移动零算法在数据已经有序时只做n次比较不发生任何交换。如果不加判断每一步都在自己交换自己虽然结果也对但赋值次数多了不少。面试时你可以顺手提一句“这个用例可以验证我的优化判断”。5.3 0的位置0在开头[0,1,2]right1时交换变成[1,0,2]right2时交换变成[1,2,0]。0在末尾[1,2,0]扫描到最后一步发现是0直接跳过数组不变。0在中间[1,0,2]right2时交换变成[1,2,0]。多个0连续[1,0,0,2]前面推演过最终[1,2,0,0]。这些用例都要在本地跑一遍尤其是连续0的用例它能帮你确认交换法会不会遗漏中间的0。实际上交换法遇到连续0时并不会对每个0单独处理只在遇到下一个非零元素时一次性把连续的0整体“甩”到后面。这是我当初手推时觉得最反直觉的一点。5.4 负数、极大值和极小值题目说的是“整数数组”所以负数也是非零元素。比如[-1,0,2,0,-3]应该变成[-1,2,-3,0,0]。比较时只能写nums[right] 0不能写成nums[right] 0否则负数和0都会被错误处理。边界上还要考虑Integer.MAX_VALUE和Integer.MIN_VALUE。它们跟0比较的结果没什么悬念交换时注意临时变量类型别写错就行。实际测试时建议把正数、负数、0混合在一起模拟真实业务数据分布不要只测全是正数的情况。这里有个经验之谈很多人会下意识把“非零”当成“正数”这是隐藏的坑。题目里说的是非零也就是! 0而不是 0或 0。一旦写成if (nums[right] 0)负数和0都会被错误地放到末尾结果完全偏离题意。5.5 可直接复用的测试用例表输入期望输出备注[][]空数组[0][0]只有一个0[1][1]只有一个非0[0,0,0][0,0,0]全0[1,2,3][1,2,3]全非0[0,1,0,3,12][1,3,12,0,0]标准用例[1,0,2][1,2,0]0在中间[1,0,0,2][1,2,0,0]连续0[-1,0,2,0,-3][-1,2,-3,0,0]负数[2147483647,0,-2147483648][2147483647,-2147483648,0]边界大数把这些用例保存成一个测试数组每次改代码后一键跑一遍能覆盖九成以上的边界问题。尤其建议在提交前跑一遍“全0”和“全非0”这两个用例能最快暴露left ! right这个优化是否正确。6. 从移动零延续出去的一类题同构变体与面试追问6.1 移除元素删掉指定值的元素并返回新长度有一道题和移动零几乎一模一样给你一个数组和一个指定值val原地移除所有等于val的元素返回移除后数组的新长度。有的版本要求保持顺序有的只要求元素在数组前段。核心代码只需要把移动零里的nums[right] ! 0换成nums[right] ! val并且不需要在末尾补0因为函数返回的是新长度数组后面的值没人关心。这正好说明移动零本质上就是“移除0之后再补0”的复合操作。如果你先把移除元素这题练透再回头看移动零会发现移动零只是多了一步“末尾补零”。反过来如果先掌握了移动零的双指针移除元素就是它的减法版。两者一起练记忆效率会高很多。6.2 删除排序数组中的重复项原地去重并返回长度另一个常见变体给定一个非递减排序数组原地删除重复出现的元素使每个元素只出现一次返回新长度。解法同样采用双指针slow指向下一个不重复元素的位置fast从1开始扫描如果nums[fast] ! nums[slow - 1]就把nums[fast]放进nums[slow]然后slow加1。这里判断条件从“等于某个特殊值”变成了“是否和上一个元素相同”但整体框架依然是一趟保序前置。你会发现移动零、移除元素、去重这三类题本质上是同一个模板right负责寻找符合要求的元素left负责接收这些元素。只要抓住这个抽象遇到新的变体时你就不需要从零开始想而是直接套模板再调整判断条件。6.3 颜色分类两指针到三指针的跃迁如果数组元素只有0、1、2三种值要求把它们按0、1、2的顺序原地排好这就是“颜色分类”题。更优解是使用三指针一个指针维护0的右边界一个指针维护2的左边界再用一个扫描指针处理当前元素。移动零相当于只有“0”和“非0”两类所以一个left指针就够了颜色分类有三类自然需要两个边界指针。从二分类到三分类思路是自然递进的。如果你面试时遇到颜色分类可以主动说“我做过移动零它是两类问题现在是三类我可以用两个边界指针来做。”这个迁移能力是面试官非常看重的。有时候面试官并不指望你一遍写出完美代码而是想看你面对新问题时能不能调取已有知识。6.4 面试官真正想听的三句话总结一下面试这道题时最稳的回答结构是三句话“我用两个指针right负责找非零元素left表示下一个非零应该放的位置一趟扫描完成时间复杂度O(n)空间复杂度O(1)。”“交换的时候left位置要么是0要么和right重合所以交换不会改变非零元素的相对顺序。”“如果0特别少可以先加一个if (left ! right)判断避免自己交换如果0特别多交换法的效率优势更明显。”这三句话覆盖了算法思路、正确性论证和常数优化基本能把面试官的问题拦住一大半。实际面试里哪怕你代码没完全写对只要这三句话讲利落面试官也愿意引导你改对代码。相反代码背得滚瓜烂熟但解释不清指针含义反而容易被判定为“背题”。最后说一个我自己刷这道题时的习惯我不会只看答案而是把推演过程完整写在草稿纸上尤其是把left和right的定义先用中文写一遍。前几天有个来问我的朋友说网上解法都能看懂但自己一写就乱。我让他先把“left是下一个非零元素该放的位置”写在注释里然后一步步画数组状态不到半小时就通了。移动零是一道很好的检视窗口如果你能一口气把暴力解、双指针解、边界情况和连续变体都讲清楚说明你真正理解了数组题的基本套路。后面再遇到“移除元素”“去重”“颜色分类”你会轻松很多。