算法：双指针解法 - 复写零

一、题目介绍

LeetCode 1089. 复写零。

给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

示例 1： 输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2： 输入：arr = [1,2,3] 输出：[1,2,3] 解释：调用函数后，输入的数组将被修改为：[1,2,3]

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 9

二、双指针原理

这道题的核心难点在于'就地修改'且不能覆盖未处理的数据。如果直接从左向右遍历并插入零，后面的元素会被不断挤出去，导致数据丢失或需要频繁移动。

解决思路通常采用两次遍历的双指针法：

1. 第一次遍历（计数）：确定扩展后的逻辑终点。我们不需要真的去移动元素，只需要知道如果所有零都复写，数组会延伸到哪里。
2. 第二次遍历（回填）：从逻辑终点往回倒序填充。这样能保证我们在写入新数据时，不会覆盖掉后面还需要读取的旧数据。

1. 当前维护指针

我们需要两个指针：

• cur：指向原数组的当前位置，用于读取数据。
• dest：指向逻辑上扩展后的目标位置，用于计算边界。

2. 维护要求

关键在于不能覆盖掉未产效元素。通过逆序维护（从后往前），我们可以安全地将数据写入到最终位置。

三、提交代码

下面是完整的 Java 实现。代码逻辑分为三步：先计算扩展后的边界，再处理边界特殊情况（如最后一个零被截断），最后倒序填充。

public void duplicateZeros(int[] arr) {
    int dest = -1;
    int cur = 0;
    
    
    
     (dest < arr.length - ) {
         (arr[cur] == ) {
            dest += ;
        }  {
            dest++;
        }
        cur++;
    }
    
    
    cur--;
    
    
    
    
     (dest == arr.length) {
        arr[dest - ] = ; 
        dest -= ;
        cur--;
    }
    
    
    
     (cur >= ) {
         (arr[cur] == ) {
            arr[dest] = ;
            arr[dest - ] = ;
            dest -= ;
        }  {
            arr[dest] = arr[cur];
            dest--;
        }
        cur--;
    }
}