1. 从一道简单题说起为什么移动零值得写一整篇笔记先交代一下背景。最近在按专题刷数组类的题目做到“283.移动零”这道题的时候我发现一个很有意思的现象这道题在力扣上标记为“简单”评论区却常年有人在问“为什么我的双指针写出来超时”“为什么交换之后顺序乱了”“为什么不能直接排序”。我身边的A同学也跟我抱怨过说自己看题解能看懂关上编辑器自己写就卡壳。这恰恰说明一个问题简单题不等于没有价值反而越是简单题越能暴露对基础技巧的理解是否扎实。移动零这个题目的描述非常简单给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。要求是原地操作不能拷贝额外数组尽量减少操作次数。你可能会想这不就是遍历一遍把0挑出来放到最后吗但如果真的动手写你会发现里面至少藏着三个考点第一如何做到原地操作不借助额外数组第二如何保持非零元素的相对顺序第三如何让时间复杂度尽可能低最好是O(n)空间复杂度O(1)。这三个考点背后指向的其实是同一类算法思想——双指针技巧。这道题本质上是双指针场景里的“快慢指针”模式只不过它用了一个相对简单的包装。把这个包装拆开你就能看到一类数组问题的通用解法。这篇笔记我不打算只贴一段能通过的代码而是想把它拆开讲清楚为什么双指针是对的为什么有些人写的双指针会有问题以及从这道题能延展出哪些值得练的变体。毕竟刷题的核心目的不是“记住答案”而是“建立模式识别能力”下次看到一个陌生题能反应过来“这题我见过本质就是快慢指针”。顺便说一下我做这道题之前已经刷过一些双指针的题目比如有序数组去重、移除元素、合并有序数组之类的。移动零放在这个序列里恰好是一个承上启下的题目它和“移除元素”是同一套逻辑的两个方向理解了移动零往回看移除元素、往前看后续的数组原地操作题思路会顺很多。2. 题面拆解与考点定位这道“简单题”到底在考什么很多人刷题有一个坏习惯拿到题目先想“我能不能用库函数一把梭”。移动零这道题确实有讨巧的办法比如用 sort 或者手动把非零元素挑出来再补零但这样做的后果就是题刷了核心能力没长进。我习惯先把题面拆成几个明确的条件和约束再倒推它到底在考什么。2.1 显式条件四条要求逐一翻译原题的约束条件可以拆成这么几条第一条把所有的0移动到数组末尾。这意味着最终数组的前面全是非零元素后面全是0而且0的个数等于原数组中0的个数。第二条保持非零元素的相对顺序。这句话是整道题最难的点。比如输入[0, 1, 0, 3, 12]最终应该是[1, 3, 12, 0, 0]1、3、12的顺序和原数组一致。如果直接排序或者用某些交换方式很可能把顺序打乱。第三条原地操作。不能 new 一个数组把非零元素按顺序塞进去再把0补在后面然后赋值回去。虽然这种做法在工程上很常见但题目明确禁止了。第四条尽量减少操作次数。这句话其实是提示你去思考最优解。所谓“尽量减少”在算法题语境里通常指时间复杂度 O(n)空间复杂度 O(1)。2.2 隐性考点这道题真正想考察的能力模型把显式条件翻译完之后我意识到这道题真正想考察的东西有三层第一层是指针思维。你能不能想到用两个指针分别承担“遍历数组”和“记录写入位置”的职责而不是依赖元素交换的蛮力做法。这个能力在后缀数组、链表操作、滑动窗口里都会反复用到。第二层是不变量维护。好用的双指针解法一定有一个不变量[0, slow)区间里存放的已经是处理过的所有非零元素。写代码的时候这个不变量必须全程成立。一旦你没有明确的不变量代码写到一半就容易乱。第三层是边界处理能力。比如数组全零、数组全非零、数组只有一个元素、0在开头、0在结尾这些边界情况能否处理得干净利落。很多人的代码在常规用例下没问题一提交就出现索引越界或答案错误基本就是边界没想清楚。2.3 一个容易被忽略的细节为什么不能直接“删0再补0”有的朋友可能会想我遍历一遍遇到0就删除最后在数组末尾补上相同数量的0不也能达到效果吗在 Python 这样的语言里list.remove(0)或者自己写循环删除确实能过。但这里有两个问题一是删除操作的复杂度。数组删除一个元素需要把后面所有元素往前移动时间复杂度是O(n)如果0很多整体就是O(n²)。题目虽没有明确惩罚高复杂度但“尽量减少操作次数”这条约束已经暗示了不希望你这么做。二是遍历过程中删除元素会导致索引错位。遍历到i位置删掉一个0后面的元素全部往前挪了一位但你的循环还在继续往i1走这样可能跳过一个本应检查的元素也可能让明明相邻的两个0只被处理了一个。这个坑我见过很多人踩。提示如果面试中你写出“删除元素再补零”的解法面试官大概率会追问一句“你能在O(n)时间内完成吗”。与其被追问后临时改不如一开始就奔着最优解去。3. 双指针解法新建数组思路先用最朴素的方式建立直觉在讲最优解之前我想先聊一个“犯规”但能帮助理解的思路新建数组法。虽然题目不允许但它对建立直觉非常有效我刷题时经常先想清楚这种朴素解法再把它优化成符合要求的写法。3.1 朴素解法全流程三遍扫描的笨办法新建数组法的流程非常直观总共分三步第一遍扫描统计数组中非零元素的个数记为count。第二遍扫描把非零元素按顺序填入一个新数组的前count个位置。第三步在新数组剩余位置全部填0。用代码表示就是这样def move_zeroes_bruteforce(nums): n len(nums) new_arr [0] * n idx 0 for num in nums: if num ! 0: new_arr[idx] num idx 1 return new_arr你可能会说这不是很简单吗确实简单。但简单背后有一个关键信息非零元素的相对顺序天然被保留了。为什么因为我们遍历原数组的顺序是从左到右遇到非零就往新数组里放这是先入先出的逻辑顺序不可能乱。这个朴素解法的时空复杂度是多少时间上需要两次完整遍历O(n)空间上额外申请了一个同样长度的数组O(n)。3.2 从朴素到原地核心冲突到底是什么现在问题来了题目不允许用额外数组那怎么把“放到新数组”这个动作改成“放到原数组自己身上”关键冲突在于当我们想把一个非零元素放到它应该在的位置时那个位置可能已经被另一个还未处理的元素占据了。这就是双指针技巧出现的根本原因——我们需要两个指针协同工作一个负责“找”一个负责“放”在同一个数组内部完成类似“搬到新数组”的效果。类比一下生活场景搬家公司搬家。朴素做法是先把所有家具搬到新房子再在新房子里摆放。原地做法是你只有一套房子需要一边腾空位置一边把家具挪到正确的位置同时不能让家具之间的相对顺序乱掉。双指针就是那个“腾挪调度员”。想通了这一点再看后面的优化解法就会觉得每条代码都有据可循而不是死记硬背。4. 快慢指针的核心推导从“搬移”到“交换”的一步之遥新建数组法的缺点很明显空间复杂度不达标。为了做到原地我引入了两个指针一个慢指针slow一个快指针fast。这两个指针都从数组起始位置出发但职责不同。fast指针负责遍历数组它的使命是找到每一个非零元素。slow指针负责记录“下一个非零元素应该放置的位置”。它们之间维持着一个不变量在遍历过程中的任何一个时刻nums[0..slow-1]都是已经处理好的非零元素序列。4.1 覆盖式写法的推导过程与代码有了上面的不变量写代码就顺理成章了。初始状态下slow 0意味着“目前还没有任何非零元素被放置好”。fast 0从数组第一个元素开始遍历。fast每遇到一个非零元素nums[fast]就把它写到nums[slow]的位置然后slow 1。这一步其实就是在模拟“把非零元素搬到新数组”的行为——只不过这次不是搬到新数组而是搬到原数组的前面去。遍历结束后nums[0..slow-1]已经包含了所有非零元素且顺序正确。接下来只需要把nums[slow..n-1]全部置0即可。代码长这样def move_zeroes(nums): n len(nums) slow 0 for fast in range(n): if nums[fast] ! 0: nums[slow] nums[fast] slow 1 for i in range(slow, n): nums[i] 0这个版本的逻辑非常清晰我在第一次接触这道题时就用的这个写法。时间复杂度是 O(n)空间复杂度是 O(1)完全符合题目要求。不过这个写法有一个小缺点它对数组里的每个非零元素都做了两次写入操作。第一次是写到前面去第二次是把原位置覆盖成0。实际上如果原位置本身就在“正确的位置”前面这个写入就是冗余的。下面我会讲到如何用交换来消除这种冗余。4.2 为什么覆盖式写法能够保证相对顺序有朋友可能会问你把非零元素往前搬怎么保证相对顺序不变答案在于fast指针的遍历顺序。fast是从左往右遍历的所以它发现的非零元素的顺序和它们在原数组中的顺序完全一致。而slow只是按顺序“接收”这些非零元素并不会重排它们。这就像一排人按顺序出队另一个人按顺序记下他们的名字最终名单的顺序自然和队伍顺序一致。这个推导看起来简单但它是整道题的灵魂。你以后会遇到很多双指针题它们的正确性证明本质上都在做同一件事证明两个指针的移动顺序与数据本身的顺序一致从而保证结果的单调性或稳定性。4.3 边界情况推演用全零、全非零、单元素验证解法写完代码不能直接提交我习惯先在脑子里过几个边界用例确认逻辑没有漏洞。第一个用例nums [0, 0, 0]。fast遍历时nums[fast]全为0所以slow始终为0循环结束后从索引0开始全部置0。最终nums [0, 0, 0]正确。第二个用例nums [1, 2, 3]。fast遍历时每个元素都非零slow一路递增到3第一个循环结束后没有置0操作。最终nums [1, 2, 3]正确。第三个用例nums [5]。fast只看一个元素非零写入nums[0]slow变1循环结束置0范围为空最终nums [5]正确。第四个用例nums [0, 1, 0, 3, 12]。这是题目给的示例手动推一遍fast0是0跳过fast1是1写入nums[0]fast2是0跳过fast3是3写入nums[1]fast4是12写入nums[2]。循环结束后从索引3开始补0最终[1, 3, 12, 0, 0]正确。边界情况全过这个解法基本就稳了。5. 优化思路用交换替代覆盖让操作次数更少覆盖式写法已经满足题目的硬性要求但它还不是最优的。如果想进一步减少数组写入次数可以用交换的思路。5.1 交换式双指针的完整推导交换式写法的核心思想是当fast指向非零元素时不直接把nums[fast]覆盖到nums[slow]而是交换nums[slow]和nums[fast]的值。这样做的结果是什么非零元素被放到了正确位置而原来slow位置上的值大概率是0也可能是一个已经处理过的非零元素被交换到了fast的位置。但是这里有一个问题如果slow位置的元素不是0而是非零元素交换会不会把顺序搞乱答案是不会。因为当我们走到这一步时slow位置的元素只有两种情况情况一slow fast说明两个指针重合交换是自己和自己交换没有任何影响。情况二slow fast说明slow位置的元素要么是0要么是一个已经被交换过来的“旧元素”而它现在已经被处理过了把它移到fast后面不影响正确性因为fast后面的区域是“尚未处理”的区域或者说是“可以安全存放临时值”的区域。核心在于slow永远指向“第一个待放置非零元素的位置”而且nums[slow]要么是0要么是一个可以被移动走的“无害元素”。5.2 两种写法的复杂度对比与代码差异交换式的代码比覆盖式短一点也更优雅def move_zeroes_swap(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1用同一个示例[0, 1, 0, 3, 12]来走一遍初始slow0。fast0值为0跳过。fast1值为1交换nums[0]和nums[1]数组变为[1, 0, 0, 3, 12]slow1。fast2值为0跳过。fast3值为3交换nums[1]和nums[3]数组变为[1, 3, 0, 0, 12]slow2。fast4值为12交换nums[2]和nums[4]数组变为[1, 3, 12, 0, 0]slow3。最终结果正确。两种写法的对比我列了一个表方便你直观感受差别和适用场景对比维度覆盖式写法交换式写法核心操作非零元素直接覆盖到 slow 位置最后统一补零非零元素与 slow 位置元素交换数组写入次数每个非零元素至少写一次最后还要写若干0只有遇到非零元素且位置不同时才写两次代码长度稍长需要第二个循环补零更短一个循环搞定相对顺序保证依赖 fast 的从左到右遍历同样依赖 fast 的从左到右遍历且交换不会破坏是否依赖 slow 位置的元素类型不依赖慢指针位置只用于写入依赖“slow 位置是0或无价值元素”这一隐含条件从算法复杂度的角度讲两者都是 O(n) 时间和 O(1) 空间差别只在常数级别。但在工程实践中交换式写法更符合“原地修改数组”的直觉面试时说出来也更讨喜。5.3 什么时候覆盖更合适什么时候交换更合适虽然交换式看起来“更优”但覆盖式并非一无是处。如果题目要求是“把所有非零元素保留到前面不关心后面的元素是什么”覆盖式更直接。比如“移除元素”这道题要求移除指定值覆盖式写法就是标准的双指针模板。但如果题目明确要求“把0移到最后”交换式更契合语义因为它不仅把非零前移还顺带把0后移了。而且交换式不会出现“写入了重复元素再覆盖”的中间状态某些场景下更安全。我自己的习惯是遇到“移动某类元素到末尾”的题优先用交换式遇到“移除某类元素”的题优先用覆盖式。这个习惯帮我在后续刷题中节省了不少思考时间。6. 从移动零到一类题这题的思维模型还能用在哪些地方移动零不是一个孤立的题目。把它彻底搞懂之后我发现它的底层模型是一类“数组原地重排”问题的通用解法。这里我挑几个我觉得最有价值的延展方向。6.1 扩展一移除元素“移除元素”这道题要求原地删除所有值等于给定值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”只不过移动零额外要求把0放到末尾而移除元素不关心后面的元素。这个抽象能力很重要。刷题不是背题而是把每一道题提炼成“我怎么判断元素是否属于应保留集合”“我如何用双指针保持不变量”然后拿这套模板去套新题。6.2 扩展二有序数组去重的双指针变体有序数组去重要求原地删除重复出现的元素使每个元素只出现一次。它的核心也是双指针只不过判断逻辑从“是否为0”变成了“是否与上一个不同”def remove_duplicates(nums): if not nums: return 0 slow 1 for fast in range(1, len(nums)): if nums[fast] ! nums[slow - 1]: nums[slow] nums[fast] slow 1 return slow这个解法里的slow起始位置是1因为第一个元素天然不需要去重。fast从1开始每次遇到“和上一个保留元素不同”的值就把它写入slow位置。你可以看到这依然是“快指针负责找慢指针负责放”的模式。6.3 扩展三颜色分类问题中的三指针再往后走如果数组里有三类元素需要分类比如“颜色分类”这道题把0、1、2排列成有序状态就需要三指针或者更精细的双指针设计。那题比移动零复杂不少但底层的“指针分工”思想是一脉相承的。我建议大家按这个路径去练习先刷“移除元素”理解覆盖式双指针再刷“移动零”理解交换式双指针然后刷“有序数组去重”理解判断条件的抽象化最后挑战“颜色分类”看看多个区域的指针如何协作。这条路径走完你对数组类双指针的把握会扎实很多之后遇到“按奇偶排序”“数组分区”类的题目基本都能一眼看穿解法。7. 我踩过的坑和总结的调试技巧最后这部分我想分享几个我在刷这道题时真实踩过的坑。有些坑很小但足以让一次提交从AC变成WA。7.1 坑一循环里忘记更新 slow 指针我第一次写交换式解法时if nums[fast] ! 0里面做了交换但忘了slow 1。结果是每个非零元素都被交换到了同一个位置后面的非零元素覆盖了前面的数组严重丢失元素。这个坑提醒我写双指针代码时每写一个“写入”或“交换”动作紧接着就要确认对应指针是否更新。这是一个原子动作不能拆开。7.2 坑二把 fast 初始化为1而不是0有的题解会把fast初始化为1理由是从第二个元素开始遍历。但移动零这道题第一个元素也可能是0需要被处理所以fast必须从0开始。如果从1开始数组[0, 0, 1]会被错误处理成[0, 1, 0]。这个细节看起来很初级但很容易被惯性带偏。我之前刷“有序数组去重”时习惯了fast从1开始回头刷移动零就顺手写成1了结果排查半天。7.3 坑三依赖语言特性的隐藏问题在 Python 里写交换nums[slow], nums[fast] nums[fast], nums[slow]非常方便。但有些语言比如 Java如果你写nums[slow] nums[fast]; nums[fast] nums[slow]第二个赋值左边已经被覆盖了就会丢失原值。正确写法是引入临时变量int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp;这个坑在跨语言刷题时特别常见。我的建议是尽量用自己熟悉的语言把逻辑跑通然后至少再过一遍其他语言的版本防止“会解题但不会换语言表达”。7.4 调试技巧用print可视化指针位置如果题目提交不过我习惯加一段打印逻辑把每一步的slow、fast和数组状态打出来。比如def move_zeroes_debug(nums): slow 0 for fast in range(len(nums)): print(ffast{fast}, slow{slow}, nums{nums}) if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 1 print(f after swap: nums{nums})对着打印结果看几乎所有逻辑错误都能一眼揪出来。这个方法对新手特别友好可以帮你建立“指针移动和数组变化”的直观印象。7.5 一个小技巧从右向左遍历时反而更好处理的题型移动零这道题是从左往右遍历的但有些类似的题目比如把某个特定值移到数组开头从左往右遍历时逻辑会绕改成从右往左遍历会简单得多。虽然移动零本身不需要这样做但我建议大家在做变体题时保持思维开放——双指针不一定都是同向移动也可以是相向移动或反向移动关键是找到正确的遍历方向。比如“有序数组的平方”这道题如果从最左端开始平方再排序复杂度是O(n log n)但如果用相向双指针从两端比较绝对值大小就能做到O(n)。这就是方向选择带来的质变。移动零这把“小刀”磨好了后面削起其他数组题的“硬骨头”会顺手很多。我在刷题过程中越来越觉得算法能力的提升不是靠题量堆出来的而是靠把每一道经典题的原理吃透然后迁移到更多场景里。希望这篇笔记对你有同样的帮助。
