LeetCode 原地复写零：双指针与逆向填充 O(n) 时间 O(1) 空间解法

一、复写零

二、思路分析

复写零这道题是让在原数组修改，如果从前向后遍历，后面的元素会被覆盖，所以我们要找到被复写的最后一个元素，然后从后往前复写。运用双指针 + 逆向填充。

1. 找到复写的最后一个数

定义两个指针：cur 遍历原数组，pre 模拟复写后的数组指针；cur==0 时，pre 向后移动两位，cur!=0 时，pre 向后移动一位（逻辑上对应复写后的位置）；当 pre>=n-1 时，停止遍历，这时，cur 指的就是要复写的最后一个元素。

边界情况：如下面这种情况，pre == n 时，说明要复写的最后一个元素是 0，这里单独处理。

将数组最后一位改为 0，也就是 n==0；cur 向前移动一位，pre 向前移动两位。

2. 开始从后往前复写

从 cur 向前遍历，cur != 0 时，就让 arr[pre] == arr[cur]； cur == 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++;
        }
        // 处理边界情况
        if (pre == n) {
            arr[n - 1] = 0;
            cur--;
            pre -= 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) 常数空间复杂度的最优表现。其中'先确定边界、再逆向操作'的思路，是解决数组原地修改类问题的关键技巧，具有较强的通用性与实用性。