双指针算法：复写零

一、题目介绍

1089. 复写零 - 力扣（LeetCode）

给你一个长度固定的整数数组 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. 前置遍历指针

首先使用一个指针 cur 从头到尾遍历原数组，同时维护一个逻辑上的写入位置指针 dest。dest 用于计算如果所有零都被复写后，最终数组的扩展长度。

2. 当前维护指针与逆序填充

确定好最终的写入边界后，从后向前进行实际的数据移动和填充。这样可以避免覆盖尚未处理的元素。

(1) 不能覆盖未处理元素

核心原则是 逆序维护。从结果的后位开始往回变，在后追赶。如果在正向遍历时发现某个零会导致越界（即 dest 超出数组长度），则需要特殊处理该位置的零。

三、代码实现

public void duplicateZeros(int[] arr) {
    int dest = -1, cur = 0;
    // 第一阶段：确定最终写入位置
     (dest < arr.length - ) {
         (arr[cur] == ) {
            dest += ;
        }  {
            dest++;
        }
        cur++;
    }
    
    
    cur--;
    
    
     (dest == arr.length) {
        
        
        arr[dest - ] = ;
        dest -= ;
        cur--;
    }   (dest > arr.length) {
        
        
        dest--;
        cur--;
        arr[dest - ] = arr[cur];
        dest -= ;
        cur--;
    }
    
     (cur >= ) {
         (arr[cur] == ) {
            arr[dest] = ;
            arr[dest - ] = ;
            dest -= ;
        }  {
            arr[dest] = arr[cur];
            dest--;
        }
        cur--;
    }
}