LeetCode 原地复写零：双指针 + 逆向填充实现 O(n) 时间 O(1) 空间

LeetCode 原地复写零：双指针 + 逆向填充实现 O(n) 时间 O(1) 空间

这道题要求我们在固定长度的数组中复写每个 0，并将后面的元素向右移动。最直接的思路是遇到 0 就插入并右移，但这样会导致 O(n^2) 的时间复杂度，且容易越界。既然题目限制原地修改且不使用额外数组，我们需要一种更聪明的方法。

核心思路：逆向填充

如果从前向后遍历，新写入的 0 会覆盖掉原本需要保留的数据。为了避免这个问题，我们可以先计算一下'逻辑上'数组扩展后的长度，找到最后一个需要被写入的位置，然后从后往前进行填充。

第一步：确定边界

我们使用两个指针：cur 用于遍历原数组，pre 模拟复写后的数组索引。

• 当 arr[cur] 不为 0 时，pre 只前进一位。
• 当 arr[cur] 为 0 时，pre 前进两位（因为 0 会被复写）。
• 一旦 pre 超过或等于数组长度 n，说明我们已经确定了复写的边界，停止扫描。

这里有个特殊情况：如果 pre 刚好等于 n，说明最后一个元素是 0，它只需要占据一个位置（因为数组长度固定），此时需要将数组末尾的元素设为 0，并调整指针回退。

第二步：从后向前填充

确定好边界后，让 cur 和 pre 都指向各自的有效终点，开始倒序遍历：

• 如果当前元素不是 0，直接复制到 pre 位置。
• 如果是 0，则连续复制两次 0 到 pre 和 pre-1 位置。
• 每次操作后，指针向前移动。

这种方法既避免了数据覆盖，又保证了只遍历两次数组，效率极高。

代码实现

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++;
        }
        
        // 2. 处理边界情况：如果最后一个元素是 0 且刚好占满
        if (pre == n) {
            arr[n - 1] = 0;
            cur--;
            pre -= 2;
        }
        
        // 3. 从后向前复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[pre--] = arr[cur--];
            } else {
                arr[pre--] = 0;
                arr[pre--] = 0;
                cur--;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n)。我们最多遍历数组两次，一次用于定位边界，一次用于填充。
• 空间复杂度：O(1)。完全在原数组上操作，没有申请额外的存储空间。

这种'先定界、后回填'的思路在处理数组原地修改问题时非常通用，值得记住。