“复写零”这道题我在很多次笔试和模拟面试里见过它。题目描述短到一眼就能看完给定一个固定长度的整数数组遇到0就把它复写一份其余元素全部右移超过数组长度的部分直接截掉而且必须原地修改。很多人看到之后觉得“这不就是个模拟吗”结果一动手就翻车新建数组的人违反空间限制用插入法的人写出了O(n²)原地正序遍历的人把还没处理的元素覆盖了。真正让这道题从“会写”变成“写对”的是双指针里那个“从后往前”的直觉和一层很容易被忽略的边界条件。这篇就把这个题完整拆开讲清楚两趟扫描的原理、边界特判到底在防什么以及同类的双指针题怎么举一反三。1. 先看懂题目复写零到底在干什么1.1 题面与示例题目本身不长翻译成人话是这样的给你一个长度固定的数组你把每一个0都变成两个0其他数字不变顺序也不变整体向右挤压凡是超出原数组长度的元素全部丢弃。关键约束是“原地修改”也就是不能另外开一个等长的数组来承接结果。举一个最典型的例子输入[1, 0, 2, 3, 0, 4, 5, 0]输出[1, 0, 0, 2, 3, 0, 0, 4]。我们拆开看逻辑展开的过程1 变成 1第一个 0 变成 0, 02 变成 23 变成 3第二个 0 变成 0, 04 变成 45 变成 5最后一个 0 变成 0, 0逻辑上完整的新序列是[1, 0, 0, 2, 3, 0, 0, 4, 5, 0, 0]长度已经变成11而原数组长度是8所以最后三个格子5, 0, 0直接被丢弃最终数组就是[1, 0, 0, 2, 3, 0, 0, 4]。没有0的情况也顺一遍[1, 2, 3]复写后还是[1, 2, 3]因为没有一个元素发生翻倍。这道题本身逻辑不复杂但它的陷阱正好藏在“原地”和“截断”这两个词上。1.2 为什么最直觉的解法反而不行正常人第一次看到这个题脑子里冒出来的多半是“那我重新建一个数组遍历原数组遇到0写两遍遇到非0写一遍最后截取前n个完事”。这个做法结果完全正确时间也是O(n)但它开辟了额外空间空间复杂度是O(n)。题目里“原地修改”这四个字直接堵死了这条路。换个思路有人会想“我直接在原数组里插入0”。以 Python 的list.insert为例每一次在位置i插入0都需要把i后面的元素整体后移一位这一步就是O(n)的。如果数组里有m个0总体复杂度逼近O(n*m)在0密度高的数据上就是O(n²)比如全0数组会卡到怀疑人生。C里用vector::insert同理。所以这道题表面上考“数组模拟”实际考的是能不能在O(1)额外空间里完成扩容式的拷贝。一旦意识到这个约束双指针几乎是注定要走的路。1.3 用“整理书架”理解原地扩容为什么从前往后会出事从后往前就不会可以想象一排书架上摆了8本书现在要求把其中所有的“0书”都变成两本其余书保持相对顺序最终还是只摆8本。如果你从左往右整理当你把第3本书复制成两本、往右塞的时候第4本书的位置会被占掉。你还没处理它呢它的原内容就被覆盖了。等你读到那个位置时原书已经没了。如果反过来从书架最右边开始整理每次把一本书放到它最终该在的位置左边那些还没移动的书完全不受影响。因为你动的是右边已经处理完的区域永远碰不到左边还没读的书。这就是这道题最核心的操作直觉目标数组比原数组长原地操作时优先从后往前写。2. 双指针切入第一趟找边界第二趟倒着写2.1 双指针在这里不是快慢而是“读指针”和“写指针”说到双指针很多人第一时间想到链表里的快慢指针或者二分查找里的左右夹逼。但数组原地修改类的题目里更常用的双指针模型其实是“读指针”和“写指针”一个指针负责遍历原始数据另一个指针负责往结果位置写入。复写0这个题里读指针和写指针的关系有点特殊因为数组要变长写指针的移动速度会比读指针快。遇到一个0时读指针往前走一格写指针却要往前走两格。正因为两个指针不同速才导致直接用一趟从头到尾的遍历无法完成——写指针会超过读指针覆盖掉还没读取的数据。解决办法很朴素既然从头到尾会越读越乱那就从尾到头。可问题又来了从尾到头写的时候写指针一开始应该落在哪个位置直接落在n-1对吗不对因为逻辑上数组扩容后的尾部并不是原数组的尾部。必须先知道扩容后哪些元素会被截断。于是就有了经典的两趟结构。2.2 第一趟扫描“虚拟扩容后”的数组确定有效前缀我们可以想象数组扩容后的样子虽然实际不能开新数组但逻辑上可以算出来。设n len(arr)zeros记录扫描到当前位置为止复写0带来的额外空间占用。每遇到一个非0元素它在扩展后序列里占1个位置每遇到一个0它在扩展后序列里占2个位置。第一趟扫描的循环条件写成while i zeros n这个条件的意思是当前这个原始元素如果写进扩容后的数组它的最后一个位置是否还能落在原数组长度之内如果能说明它活着如果i zeros已经到边界甚至超过边界说明它以及它后面的所有元素都会在截断中消失。以[1, 0, 2, 3, 0, 4, 5, 0]为例我做一个完整追踪表步骤iarr[i]进入前 zerosi zeros是否满足 n8操作后 zeros10100是保留021001是保留132213是保留143314是保留154015是保留265427是保留276528否退出2循环退出时i 6说明索引6和7的元素都会被截断有效前缀是索引0到5这一段。把i--之后i 5就是最后一个存活的原始元素下标。这一步的本质是用虚拟下标去卡边界找出哪些原始数据能活到最终数组里。2.3 第二趟从有效前缀末尾开始倒着复写当第一趟确定了最后一个存活的原始元素的坐标之后第二趟就很直接了。初始化写指针write n - 1也就是最终数组真正的尾部。读指针read从第一趟算出的有效前缀末尾开始。每一轮循环做这样的事如果arr[read]是0就往arr[write]和arr[write - 1]各写入一个0写指针前进两格如果arr[read]不是0就把原值写到arr[write]写指针前进一格读指针每次前进一格。因为读指针从有效前缀的末尾出发写指针从数组末尾出发而有效前缀的末尾一定不晚于数组末尾所以写指针始终在右侧就算连续写两个0写指针左移两格也不太可能越过读指针。即使某个极端情形下写指针短暂到达读指针附近读指针此时已经不会再需要那些位置上的原始数据了。整个遍历过程天然避免了覆盖未读数据。还是[1, 0, 2, 3, 0, 4, 5, 0]第一趟结束后zeros 2有效前缀末尾是索引5。第二趟从read 5write 7开始倒着写一圈就能得到[1, 0, 0, 2, 3, 0, 0, 4]。3. 完整解题方案与多语言实现3.1 分步骤拆解算法流程整个算法整理成三步第一趟统计用zeros记录复写0带来的额外占用循环条件卡住数组边界找出有效前缀的末尾位置。边界特判如果最后一个存活元素正好是0且它只占据了数组的最后一格那么这个0只能复写一次需要单独处理。这是全题最容易出错的地方。第二趟倒写读指针从有效前缀末尾向左走写指针从数组末尾向左走根据当前元素是否为0决定写一格还是写两格。3.2 边界特判到底在防什么很多人的代码死在这一步。看一个具体例子输入[1, 0, 0, 2]第一趟扫描后zeros 2i最终指向索引2。这里i zeros 2 2 4恰好等于n 4。这说明最后一个存活元素是索引2的0但它在逻辑展开后占两个位置而数组只剩末尾一个空位了。也就是说这个0只能写一次到arr[3]第二个0要被截断。如果不在第二趟开始前把这个事处理掉倒写时读指针读到索引2的0会往arr[3]和arr[2]连写两个0结果把数组搞得面目全非。正确的特判是if zeros 0 and i zeros n: arr[n - 1] 0 write - 1 read - 1先把能写的那一个0放到数组末尾同时写指针和读指针各前移一格。这样索引2的0就被视为“已经完成了单次复制”不会再进入第二趟循环。推演一遍特判后 read 指向索引1write 指向索引2读到索引1的0往arr[2]和arr[1]写0读到索引0的1往arr[0]写1最终数组是[1, 0, 0, 0]和人工推演完全一致。3.3 Python 实现def duplicateZeros(arr): n len(arr) zeros 0 i 0 # 第一趟找出有效前缀边界 while i zeros n: if arr[i] 0: zeros 1 i 1 # i 此时指向第一个不可能存活的位置减1得到有效前缀末尾 i - 1 write n - 1 # 边界特判最后一个有效元素是0且只能写一次 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 # 第二趟从后往前倒写 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1这段代码里最值得注意的两个地方第二趟的循环条件用write 0而不是i 0可以防止读指针越界边界特判里写指针和读指针都要同步前移。3.4 C 与 Java 实现C版本void duplicateZeros(vectorint arr) { int n arr.size(); int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write] 0; write--; arr[write] 0; write--; } else { arr[write] arr[i]; write--; } i--; } }Java版本public void duplicateZeros(int[] arr) { int n arr.length; int zeros 0; int i 0; while (i zeros n) { if (arr[i] 0) zeros; i; } i--; int write n - 1; if (zeros 0 i zeros n) { arr[write] 0; write--; i--; } while (write 0) { if (arr[i] 0) { arr[write--] 0; arr[write--] 0; } else { arr[write--] arr[i]; } i--; } }三种语言的核心逻辑完全一致只是语法细节不同。Java里连续两次write--简写在一行里注意别把指针移动次序搞反就行。3.5 复杂度分析第一趟循环最多扫描到n个元素就停第二趟倒写也只需要处理有效前缀长度范围内的元素。两趟加起来是严格O(n)即使是全0数组第一趟也会因为i zeros n快速退出。空间方面只用了zeros、i、write三个整数变量没有开辟任何数组空间复杂度O(1)。时间上可能有人会问第二趟循环里遇到0会连写两次会不会多一次操作不会因为写入这两个0正好对应它复写后的两个格子写入次数和最终数组长度是一一对应的。总体操作次数仍然和数组长度成正比。4. 最容易翻车的边界条件4.1 末尾是0复写一次还是两次这是整道题最大的坑单独拿出来说。判断逻辑是如果最后一个“存活”的原始元素刚好是0而且它复写后占两个格子但数组只剩一个空位那么这个0只能复写一次。写成代码就是i zeros n这个条件。我用四个例子做个速查表输入逻辑展开后前n位代码结果说明[1, 0, 0, 2][1, 0, 0, 0][1, 0, 0, 0]最后一个存活元素0只写一次[0, 0, 1][0, 0, 0][0, 0, 0]边界0占据最后格子[0, 0, 0][0, 0, 0][0, 0, 0]前两个0占4格只剩3格[0, 1, 0][0, 0, 1][0, 0, 1]第二个0直接被截断这几个用例看着差不多但如果不做边界特判反应在结果上就是末尾多了一个0或中间少了一个0。4.2 空数组和单元素数组空数组就不说了什么循环都不会进入直接返回。单元素数组要看元素是不是0[0]复写后逻辑上是[0, 0]截断成[0]。第一趟扫描时i zeros 1i0时遇到0zeros变成1i变成1退出i1减到0i zeros 1 n触发特判把arr[0] 0后 write变成-1read变成-1第二趟不执行最终是[0]。[3]没有0第一趟扫描后 zeros0不触发特判第二趟把arr[0]原样写回最终[3]。这两个小用例用来验证代码的健壮性特别好刷完题之后可以顺手测一下。4.3 手工推演一个全0数组全0数组是很多人写崩的场景。拿[0, 0, 0]来说逻辑上复写后是6个0截断成3个0看起来结果没变化但代码必须正确处理。第一趟扫描i0zeros0进入循环arr[0]0zeros变成1i变为1i1zeros11 1 3成立arr[1]0zeros变成2i变为2i2zeros22 2 3不成立退出退出后i 2减一变成1。此时i zeros 1 2 3 n触发特判arr[2] 0write变成1i变成0。第二趟从 i0 开始读到一个0写两格到arr[1]和arr[0]。最终仍然是三个0。如果不做特判第二趟从 i1 开始写到后面就会发现 write 已经变负但读指针还有元素没处理或者最后多写一个0导致数组被写穿。运行时报错还是小事静默返回错误结果更可怕。4.4 常见错误速查表错误写法错误后果正确做法第一趟循环用for i in range(n)多统计被截断的0有效前缀偏移用while i zeros n卡边界第二趟直接从read n - 1开始末尾原始数据可能被错误复制中间被覆盖从有效前缀末尾开始边界0不做特判数组末尾出现连续两个0以外的错位用i zeros n判断并单写一次第二趟条件写成while i 0写指针可能已经出界但读指针仍有残留触发越界用while write 0特判后只移动读指针不移动写指针边界0被写两次后面数据错位读指针和写指针都前移一格5. 一法通百法双指针题的迁移思路5.1 三种双指针模型数组题里的双指针大致能分成三类快慢指针一个指针走得快一个走得慢常用于链表找环、数组去重。左右对撞指针一个从左边走一个从右边走常用于有序数组求和、反转数组。读写指针一个负责读原数组一个负责往结果位置写常用于原地删除、原地移动。“复写零”属于第三种。这类题的核心判断方式是如果目标数组比原数组短一般从前往后用快慢指针如果目标数组比原数组长基本要从后往前用读写指针。5.2 和“移动零”“原地去重”的对比原地去重这道题目标数组比原数组短所以用一个慢指针指向“下一个不重复元素该放的位置”快指针从头扫描原数组发现新元素就写过去。这种从前往后没问题因为快指针一定在慢指针前面或相等。“移动零”也是同一个道理先把所有非零元素集中到前面再把后面全部补0。它不需要扩容所以从前往后写完全安全。“复写零”反过来目标长度变长每一个0都要多占一个位置。此时从前往后写写指针会超过读指针覆盖未读数据所以必须倒过来。合并两个有序数组也是这个思路第一个数组尾部预留了足够空间从后往前比较并写入谁大谁先放根本不需要额外数组。总结成一句话目标变长先找边界再从后往前写目标变短快慢指针直接从前扫。5.3 面试里怎么快速识别这类题你看一个数组题如果要求原地修改先把最终长度和原始长度做比较。最终长度大于原始长度八成要用到“先扩容再倒写”的思路最终长度小于或等于原始长度大概率是快慢指针的前向覆盖。“复写零”表面上是模拟实际是“扩容式原地修改”的入门题。理解了它再去做“合并两个有序数组”“字符串中的空格替换”这类题就会顺畅很多因为它们共用同一套从后往前的直觉。6. 面试现场怎么在几分钟内讲清楚解法6.1 先给暴力解再谈优化面试遇到这题不用一上来就甩双指针。先快速说一句“最直接的办法是新开数组遇到0写两遍时间复杂度O(n)但空间O(n)不符合原地要求”。这能让面试官知道你对复杂度有意识。然后说第二层“如果要在原地做就必须考虑覆盖问题。数组要变长正序写会覆盖后续元素所以大概率倒序但倒序前必须知道哪些元素能活到最终数组里于是第一趟先数0、卡边界。”6.2 把双指针方案压缩成三句话整个方案用三句话就能说清第一趟用i zeros n扫描找出有效前缀的末尾位置。如果末尾元素是0且它只够写一次单独处理这个边界0。第二趟从有效前缀末尾出发读指针和写指针一起向左移动遇0写两格遇非0写一格。口述时强调“读指针和写指针不同速”“从后往前不会覆盖未读数据”“边界0只写一次”这三个点面试官基本就会点头。6.3 我个人最推荐的代码模板我在面试和平时刷题时习惯用的就是上面那套 Python 模板。它有几个好处第一趟直接卡边界不像某些写法要先数完所有0再二次判断边界特判用i zeros n一目了然第二趟循环条件用write 0从根本上杜绝越界。def duplicateZeros(arr): n len(arr) zeros 0 i 0 while i zeros n: if arr[i] 0: zeros 1 i 1 i - 1 write n - 1 if zeros 0 and i zeros n: arr[write] 0 write - 1 i - 1 while write 0: if arr[i] 0: arr[write] 0 write - 1 arr[write] 0 write - 1 else: arr[write] arr[i] write - 1 i - 1这个模板可以直接背更重要的是每次写完都手动跑一遍[1, 0, 0, 2]、[0, 0, 1]、[0, 0, 0]、[1, 0, 2, 3, 0, 4, 5, 0]这四个用例基本就能确认边界处理没有问题。6.4 刷题建议与复盘心得这道题很适合放进“数组原地操作”专题里反复练习。第一次做建议先不看题解自己把正序的失败过程推演一遍感受数据被覆盖的瞬间第二次做再去看双指针解法重点理解第一趟为什么能卡边界第三次做可以把代码默写出来并主动给面试官讲“如果最后一个有效元素是0会怎样”。我自己带人刷题时发现最容易卡住的地方不是双指针本身而是那个边界特判。很多人第一趟扫描写对了但第二趟忘记处理“只够写一次的0”导致结果在末尾多出一个错位。把[1, 0, 0, 2]这个用例刻进脑子里这个坑基本就不会再踩。“复写零”这类题还有一个隐藏价值它逼你跳出“从前往后”的思维惯性。实际开发里处理缓冲区扩容、日志滚动、历史版本合并时从后往前写都是一个很实用的技巧。刷题的价值有时候不在记住某个模板而在把这种“倒过来想”的直觉训练成本能。