本文聚焦 LeetCode'原地复写零'经典题目，核心需求是在固定长度数组中复写每个 0 并右移其余元素，且需满足原地修改、不使用额外数组空间的约束。正向遍历易导致后续元素被覆盖，为此详解双指针 + 逆向填充的优雅解法。
一、问题描述
给定一个固定长度的整数数组 arr，将数组中出现的每个 0 都复写一遍，并将其余元素向右平移。注意：不能在超出原数组长度的地方写入元素，且必须原地修改输入数组，不能使用额外的空间。
二、思路分析
这道题最直观的想法是遇到 0 就插入，但这样会导致后面的元素不断移动，效率低下甚至无法在 O(1) 空间内完成。关键在于：如果从前往后处理，新写入的 0 会覆盖掉原本需要保留的数据。
因此，我们需要先确定最终数组的边界在哪里，然后从后往前进行填充。这样可以保证我们不会覆盖掉还未处理的元素。
1. 确定复写边界
定义两个指针：
cur：遍历原数组的指针。pre：模拟复写后数组的指针（指向逻辑上的末尾）。
遍历规则如下：
- 当
arr[cur] == 0时，pre向后移动两位（因为 0 会被复写两次）。 - 当
arr[cur] != 0时，pre向后移动一位。
当 pre >= n - 1 时，说明已经触及或超过了数组边界，此时 cur 指向的就是最后一个需要处理的元素。
这里有一个特殊的边界情况：如果 pre 恰好等于 n，说明最后一个要复写的元素是 0，且它占据了数组的最后一位。这种情况下，我们需要单独处理，将数组最后一位设为 0，并将 cur 向前回退一位。
2. 逆向填充
确定了边界后，从 cur 开始向前遍历：
- 如果当前元素不为 0，直接将其复制到
pre位置，然后双指针同时前移。 - 如果当前元素为 0，则需要在
pre和pre-1位置都填入 0，然后双指针前移。
三、代码实现
class Solution {
public void duplicateZeros(int[] arr) {
int cur = 0, pre = -1, n = arr.length;
// 1. 找到要复写的最后一个元素
while (cur < n) {
if (arr[cur] == 0) {
pre += 2;
} else {
pre++;
}
if (pre >= n - 1) {
break;
}
cur++;
}
// 处理边界情况：如果 pre == n，说明最后一个元素是 0 且刚好占满最后一位
if (pre == n) {
arr[n - 1] = 0;
cur--;
pre -= 2;
}
// 2. 开始从后向前复写
while (cur >= 0) {
if (arr[cur] != 0) {
arr[pre--] = arr[cur--];
} else {
arr[pre--] = 0;
arr[pre--] = 0;
cur--;
}
}
}
}
四、复杂度分析
- 时间复杂度 O(n)：只需要遍历数组两次，第一次定位边界，第二次逆向填充。
- 空间复杂度 O(1)：使用的原数组，没有额外分配空间。
五、总结
本解法通过双指针先定位复写边界，再逆向填充数组，既避免了正向遍历的元素覆盖问题，又实现了 O(n) 线性时间复杂度与 O(1) 常数空间复杂度的最优表现。其中'先确定边界、再逆向操作'的思路，是解决数组原地修改类问题的关键技巧，具有较强的通用性与实用性。
