算法实战：双指针解决复写零问题

算法实战：双指针解决复写零问题

题目背景

LeetCode 1089 题要求我们处理一个整数数组 arr，将其中出现的每个零都复写一遍，并将其余的元素向右平移。关键点在于数组长度固定，超出部分直接丢弃，且必须就地修改（In-place），不能返回新数组。

示例： 输入：[1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4]

核心思路：双指针

暴力解法每次遇到零就右移后续元素，时间复杂度会达到 O(N²)。利用双指针可以将复杂度优化到 O(N)。

第一阶段：确定边界

我们需要先知道哪些元素会被保留在最终数组中。使用两个指针：

• cur：遍历原数组的当前索引。
• dest：计算如果进行复写操作后，逻辑上的目标位置。

当 dest 超过或等于数组长度时，说明我们已经找到了最后一个需要处理的元素。此时 cur 指向的位置就是原数组中参与最终结果映射的最后一个有效元素的下一位。

第二阶段：逆序填充

确定了边界后，我们从后往前复制元素。这样做是为了避免覆盖尚未处理的元素。

这里有一个细节需要注意：如果 dest 刚好等于数组长度，说明最后一个被复写的零正好填满数组末尾；如果 dest 大于数组长度，说明最后一个零被截断了，不需要写入第二个零，只需写入第一个即可。

代码实现

下面是经过优化的 Java 实现，重点处理了边界条件和越界情况。

public void duplicateZeros(int[] arr) {
    int n = arr.length;
    int i = 0; // 扫描指针
    int j = 0; // 逻辑长度指针

    // 第一阶段：计算逻辑长度，找到边界
     (j < n) {
         (arr[i] == ) {
            j += ;
        }  {
            j++;
        }
        i++;
    }

    
    
     (j > n) {
        i--; 
        j -= ; 
    }  {
        
        
        
        
        
    }

    
    
    i = ;
    j = ;
     (j < n) {
         (arr[i] == ) j += ;
         j++;
        i++;
    }

    
    
     (j > n) {
        i--;
        j -= ;
    }  {
        
        
        
        
        i--;
        j = n - ;
    }

    
     (i >= ) {
         (arr[i] == ) {
            arr[j] = ;
            j--;
             (j >= ) arr[j] = ;
            j--;
        }  {
            arr[j] = arr[i];
            j--;
        }
        i--;
    }
}