2. 题目拆解复写零到底在考什么2.1 题目的真正要求是什么如果你第一次看到“复写零”这道题大概率会被它简洁的题面骗了给定一个固定长度的整数数组遇到 0 就在它后面再写一个 0其余元素依次右移超出数组长度的部分直接丢弃要求原地修改不使用额外数组。听起来就是个简单模拟确实核心语义不复杂。但它真正的考点藏在一个词里——原地。这意味着你不能新开一个数组把“展开后”的结果算好再拷回去。只能在原数组上腾挪把每个元素放到它最终该待的位置。很多初学者第一次写的时候脑子里的思路是“正着扫遇到 0 就把后面全部右移一位再补一个 0”这种方式毫无疑问能做对但时间复杂度直接变成 O(n²)而且写出来容易在连续多个 0 的连锁移位中把自己绕晕。这道题的价值就是逼你放弃“物理模拟”转而用“指针规划位置”的思维去解决。我习惯把这类题归为“数组搬迁题”。它表面上是数组操作本质上是两件事先搞清楚每个元素的最终位置再一次性搬迁完成。如果你之前对双指针的理解还停留在“一个从头、一个从尾夹逼”的层面那这道题正好可以补上“双指针同步从右向左移动”这个重要场景这也是为什么我建议所有准备面试的人把它当作双指针专题的必修题。2.2 为什么暴力解法必然踩中覆盖陷阱我们来做个最直观的模拟。假设数组是[1, 0, 2, 3]正着扫第一个是 1不动第二个是 0于是要把后面所有元素右移一位变成[1, 0, 0, 2, 3]但数组长度只有 4所以最后一个 3 被挤出去变成[1, 0, 0, 2]。看起来没问题可一旦遇到连续 0麻烦就来了。比如[1, 0, 0, 2]正着扫到第一个 0右移后变成[1, 0, 0, 0]注意原来的第二个 0 已经被移位压到索引 2 了但你的扫描指针如果还机械地往后走很可能会再次处理这个“新移过来的 0”导致重复复写结果得到[1, 0, 0, 0]而不是正确结果[1, 0, 0, 0, 2]截断后为[1, 0, 0, 2]等等这里要仔细算——[1, 0, 0, 2]复写正确结果是[1, 0, 0, 0, 0, 2]截断到长度 4 是[1, 0, 0, 0]。所以正序模拟虽然每步都能移动但指针和数组内容在同时变化状态非常容易失控。真正致命的问题还不是逻辑复杂而是性能。每次遇到 0 都要把后面一串元素右移如果数组里全是 0一次右移就是 O(n)整体 O(n²)。在面试场景下写完这种解法面试官基本会追问“能不能 O(n)”等于白写。这就是我常说的有些题暴力解法不是不能用而是它暴露了你没有建立“时空权衡”的意识。2.3 先建立“最终布局”的直觉在动手写代码之前我建议你先做一件事拿笔在纸上把“展开后但不截断”的完整数组画出来再用一竖线标出截断位置。例如[1, 0, 2, 3, 0, 4, 5, 0]其中有 3 个 0所以展开后长度是 8 3 11。展开完整结果是[1, 0, 0, 2, 3, 0, 0, 4, 5, 0, 0]但真实数组只有 8 个位置所以截断后是[1, 0, 0, 2, 3, 0, 0, 4]注意看原数组末尾的 0 和 5 都被挤出去了甚至末尾那个 0 复写出来的两个 0 也都在截断范围之外。这意味着不是每个 0 都会被完整复写也不是每个原数组元素都会被保留。这个直觉特别重要因为很多错误代码就是默认“所有元素都要写进结果”结果在边界上整体错位。2. 核心转折倒着遍历为什么能救场2.1 从右往左写的本质原因既然正序右移会覆盖还没处理的元素那反过来想如果我从右往左写写到某个位置时它左边的内容还没被覆盖右边已经处理完的区域即使被改写也没关系因为那里已经不需要再看原始值了。这就像搬家你要把旧房间里的家具按顺序搬到新房间。如果新房间和旧房间是同一个房间原地你从门口往里搬先进去的家具会挡住后面的但如果你从最里面开始往外搬每搬一件身后空出来的地方就可以随便放新东西因为那些位置已经不会再用了。双指针倒序写的核心就是这个“从里往外搬”的思路。具体来说我们需要两个指针读指针 i 从原数组末尾开始写指针 j 从“展开后数组的末尾”开始。i 负责读原始值j 负责写入最终位置。因为展开后数组比原数组长j 一开始会在真实数组外面所以前面的若干次操作其实是在“丢弃”那些超出长度的元素。2.2 第一次遍历先数零确定写指针起点为什么必须先数零因为只有知道一共有多少个 0才能算出“展开后数组”的长度从而确定 j 的初始位置。公式很简单展开后长度 原数组长度 0 的个数。用变量表示就是newLen n zeroCount写指针 j 初始化为newLen - 1也就是展开后数组的最后一个索引。举个例子[1, 0, 2, 3, 0, 4, 5, 0]n 8zeroCount 3newLen 11j 10。真实数组最大索引只有 7所以 j 10, 9, 8 这三步操作对应的都是“将被截断掉的位置”这正好对应展开后数组末尾那三个被丢弃的元素。这一步是 O(n) 的没有任何额外空间只做一个累加计数。很多同学会问能不能不数零直接用 i 和 i 的关系推算 j其实也可以但需要额外维护“当前已遇到的 0 数量”代码反而更绕。先数零是实现清晰度最高的方案我建议新人就用这个。2.3 第二次遍历双指针同步向左移动现在进入核心逻辑。从右往左每一步都做同一件事把 i 指向的元素“展开”到 j 指向的位置然后根据当前元素是不是 0决定 j 是往前跳一格还是两格。具体规则如下如果arr[i] ! 0这个元素在展开后只占一个位置把arr[j]写成arr[i]然后i--j--。如果arr[i] 0这个 0 在展开后占两个位置应该把arr[j]和arr[j-1]都写成 0然后i--j - 2。如果j n说明要写入的位置已经超出真实数组范围这个元素会被截断丢弃所以不写只移动指针。注意第三点必须放进每一步的判断里。因为 j 从n zeroCount - 1开始一开始必然在数组外面如果这时候贸然写arr[j]下标直接越界。正确的态度是把 j 当作一个“虚拟坐标”它允许暂时大于 n - 1只有当它落在[0, n-1]区间内才真正执行写入。2.4 边界对齐最后一个 0 是最大的坑倒序遍历虽然思路清晰但有一个细节极其容易翻车当原数组末尾元素是 0 时这个 0 的复写位置可能恰好跨在截断边界上。拿刚才的例子继续看原数组最后一位是 0它在展开后数组中的两个位置是 9 和 10都大于 n - 1 7所以这个 0 根本不会被写入——它已经“滚出”数组了。但如果我们朴素地理解“遇到 0 就写两遍”可能会在 i 指向末尾 0 时强行写两次哪怕 j 已经小于 n也会把错误的值写到前面去。为了彻底解决这个隐患我的建议是在代码里不要区分“这是不是最后一个 0”而是统一用j n来兜底。每一步先判断 j 还在不在真实范围内在就写不在就跳过。这样无论末尾有多少个 0、无论截断边界怎么切都能自动对齐。这个“用位置判断、而不是用元素值判断”的思路是双指针题里非常通用的一种防御性写法。3. 手把手实操完整代码与关键写法3.1 算法步骤的伪代码表达把上面的思路整理成可执行的伪代码一共三步1. 统计数组中 0 的个数记为 zeroCount。 2. 设 n 数组长度读指针 i n - 1写指针 j n zeroCount - 1。 3. 进入循环条件是 i 0 a. 如果 arr[i] 0 - 若 j n把 arr[j] 置为 0。 - j 向左移一格。 - 若 j n把 arr[j] 置为 0。 - j 再向左移一格。 b. 否则arr[i] ! 0 - 若 j n把 arr[j] 置为 arr[i]。 - j 向左移一格。 c. i 向左移一格。这个伪代码看起来是“遇到 0 写两次”但其实每次都检查了j n所以末尾被截断的 0 会自动变成“白跑一次指针移动而不写入”。理解这一步边界问题就解决了一大半。3.2 Python 实现版本def duplicateZeros(arr): n len(arr) zero_count arr.count(0) i n - 1 j n zero_count - 1 while i 0: if arr[i] 0: if j n: arr[j] 0 j - 1 if j n: arr[j] 0 j - 1 else: if j n: arr[j] arr[i] j - 1 i - 1这段代码有一个值得注意的点Python 的负数索引问题。j在移动过程中会不断减小可能变成负数。一旦j为负if j n为真就会执行arr[j] ...而arr[-1]在 Python 里是合法索引但指向的是数组最后一个元素这就造成了隐蔽的错误。所以 Python 版本里必须把判断写成if 0 j n而不能只写if j n。这是我实际调试中踩过的坑也是 Python 写数组题时经常被忽略的“语言特性陷阱”。正确的写法如下def duplicateZeros(arr): n len(arr) zero_count arr.count(0) i n - 1 j n zero_count - 1 while i 0: if arr[i] 0: if 0 j n: arr[j] 0 j - 1 if 0 j n: arr[j] 0 j - 1 else: if 0 j n: arr[j] arr[i] j - 1 i - 13.3 Java 与 C 实现版本Java 和 C 的数组没有负数索引问题但要注意的是 Java 中int j n zeroCount - 1可能很大不过因为是 int 直接计算数组长度限制在 10000 左右时不会溢出可以放心用。public void duplicateZeros(int[] arr) { int n arr.length; int zeroCount 0; for (int x : arr) { if (x 0) zeroCount; } int i n - 1; int j n zeroCount - 1; while (i 0) { if (arr[i] 0) { if (j n) arr[j] 0; j--; if (j n) arr[j] 0; j--; } else { if (j n) arr[j] arr[i]; j--; } i--; } }C 版本几乎一样只需要把arr.length换成容器接口void duplicateZeros(vectorint arr) { int n arr.size(); int zeroCount 0; for (int x : arr) { if (x 0) zeroCount; } int i n - 1; int j n zeroCount - 1; while (i 0) { if (arr[i] 0) { if (j n) arr[j] 0; j--; if (j n) arr[j] 0; j--; } else { if (j n) arr[j] arr[i]; j--; } i--; } }这里多说一句经常有同学问为什么不用for循环。因为一次循环里 j 可能减 1 也可能减 2步长不固定用while加手动控制是最直接的。强行用for要么写j 步长要么再嵌一个分支反而增加理解成本。3.4 复杂度与正确性分析时间复杂度两次遍历都是 O(n)一次数零一次倒序写入总时间 O(n) O(n) O(n)。空间复杂度只用到了几个常量变量没有额外数组所以是 O(1)。为什么这个算法是正确而不是“碰巧对”我们可以从数学上稍微验证一下。设原数组长度为 n0 的个数为 c展开后数组长度为 n c。由于实际只能保留前 n 个元素那么被丢弃的部分正好是展开后数组的最后 c 个元素。双指针从右往左j 从 n c - 1 出发前 c 次移动无论写不写都是在消耗“超出真实数组”的坐标等 j 进入[0, n-1]后每个写入的位置都对应展开后数组的某个确定位置且由于是从右往左写入时不会破坏尚未处理的左侧数据。因此算法正确性成立。4. 常见问题与排查技巧实录4.1 覆写导致数据丢失典型错误范例我在带模拟项目 X 的同学调试时见过最典型的一个错误就是把倒序写成正序。正序模拟的处理方式通常是这样遇到 0就把 i 后面的元素全部右移然后在 i1 位置补 0i 跳过补的 0。这种写法在[1, 0, 2, 3]上能跑通但遇到[0, 0]会变成[0, 0, 0, 0]截断后是[0, 0]正确结果也是[0, 0]但如果你没有正确跳过新复写的 0就可能变成[0, 0, 0, 0]或死循环。根本原因就是数组在原地被修改后指针的“下一个位置”已经不再是逻辑上的下一个元素。这种错误直接暴露了对“读和写共用同一块内存”的风险意识不足。我的建议是如果非要用正序先把所有元素的值保存在一个新数组里但如果目标是 O(1) 空间就必须换到倒序思路。没有第三条路。4.2 数组越界边界条件排查倒序写法最常见的报错是ArrayIndexOutOfBoundsException或 Python 的IndexError。原因几乎都是没有处理j n的“虚拟写阶段”。举个例子如果数组是[1, 1, 1, 1]zeroCount 0j 初始就是 n - 1不会越界但如果数组是[0, 0, 0, 0]zeroCount 4j 初始 4 4 - 1 7真实数组索引最大是 3直接写arr[7]必然越界。排查这类问题我的经验是在循环里加一个打印i和j的调试语句手动跑一遍样例观察 j 从 7 逐步降到 3 的过程你很快就会发现前 4 次迭代都在“空转”。一旦理解了这个空转阶段越界问题就自然消失了。4.3 测试用例设计清单如何验证你的代码真的对了分享一个我常用的测试用例组合覆盖了这道题的所有关键边界用例类型输入预期输出它覆盖了什么无 0[1, 2, 3][1, 2, 3]零计数为 0j 与 i 同步单个 0 在开头[0, 1, 2][0, 0, 1]常规复写无截断单个 0 在末尾[1, 2, 0][1, 2, 0]末尾 0 被截断只算一次位置消耗连续多个 0[0, 0, 1][0, 0, 0, 0, 1]截断为[0, 0, 0, 0]连续 0 的两次写入全 0[0, 0][0, 0]j 大量空转纯边界末尾 0 且前面有 0[1, 0, 2, 0][1, 0, 0, 2]混合边界最易错我建议你把这些用例逐一带入代码走一遍。尤其是“单个 0 在末尾”这个用例很多人会误算出[1, 2, 0, 0]因为总觉得“遇到 0 必须写两遍”实际上第二个 0 的位置是数组长度之外已经丢弃了。4.4 变体与扩展如果题目换成链表怎么办这道题练完之后我一般会引导同学思考一个变体如果数据结构从数组换成单向链表要求在每个值为 0 的节点后面插入一个值为 0 的新节点你会怎么做链表的答案反而简单得多遍历时遇到 0就原地insert一个新节点不需要考虑覆盖也不需要双指针因为链表节点是动态分配的插入不会覆盖已有节点。这个对比恰好说明一个道理双指针不是万能的它解决的是“固定容器大小下的原地搬迁”问题。容器本身能扩容问题难度就直接降维了。另一个常见变体是如果不要求原地允许使用额外数组那么直接一趟扫描生成新数组即可时间复杂度 O(n)空间复杂度 O(n)。这种解法可以作为“验证正确答案”的对照组我经常写一版暴力对照再用双指针版本跑随机测试对比结果确保优化版本没有改错逻辑。5. 个人经验与一点实战心得双指针这类型题目我刷了不下五十道从数组到字符串再到链表绕来绕去其实就几个核心模型左右夹逼、快慢指针、同步位移。复写零属于“同步位移”这一模型里最适合入门的题目因为它没有复杂的数学条件也不依赖单调性你只需要牢牢抓住“虚拟长度 右向左写 越界空转”这条主线。我实际写这道题的时候第一次提交就因为没处理j n越界挂了第二次处理了越界但忘了 Python 负数索引问题第三次才完全跑对。所以我给新人的建议是别看这题简单所有边界全踩一遍比看十遍题解都管用。你可以故意写错几次观察出错的下标再回到为什么倒序、为什么数零这些基本问题上来这时候你的理解会比直接抄答案深入得多。把这题的思路吃透之后碰到类似的题目比如“合并两个有序数组到第一个数组的末尾”“原地删除重复元素保留 K 个副本”你都会发现它们共享同一套底层逻辑先用某种方式算出最终布局再选择正确的遍历方向最后用指针控制写入范围。复写零就像这套方法论的一个浓缩样板值得你反复品。