目录一、题目解析二、算法原理双指针法步骤1找最后一个“复写”的数步骤2处理边界情况步骤3从后往前复写三、代码实现Java四、复杂度分析五、总结OJ链接https://leetcode.cn/problems/duplicate-zeros/description/今天学习了LeetCode第1089题《复写零》这道题要求我们在长度固定的数组里把每个0都复写一遍也就是变成两个0其他元素向右平移而且不能超出数组长度。题目还强调要就地修改不返回新数组。下面我把思路理清楚~一、题目解析先看题目描述给定整数数组arr将出现的每个0复写一遍比如[1,0,2]变成[1,0,0,2]但数组长度固定所以超出的元素会被截断其余元素右移。注意不要越界写入就地修改。举个例子示例1输入arr [1,0,2,3,0,4,5,0]输出[1,0,0,2,3,0,0,4]因为最后一个0复写后超出长度所以只保留前面的部分。示例2输入arr [1,2,3]输出[1,2,3]没有0所以不变。二、算法原理双指针法笔记里说先想“异地”操作比如新建一个数组来放结果再优化成“就地”的双指针操作。核心是找到最后一个需要复写的0的位置然后从后往前填充。步骤1找最后一个“复写”的数用两个指针cur遍历原数组和dest记录复写后的位置。如果arr[cur]是0dest加2因为0要复写占两个位置如果arr[cur]不是0dest加1占一个位置当dest超过或等于数组长度n-1时停止说明找到最后一个需要复写的数了。步骤2处理边界情况如果dest刚好等于n比如数组最后一个元素是0复写后dest会到n这时候要把最后一个位置设为0然后cur和dest回退cur--dest - 2。步骤3从后往前复写现在cur指向最后一个需要复写的数dest指向结果数组的最后一个位置。从后往前遍历如果arr[cur]不是0就把arr[cur]放到dest位置然后cur--dest--如果arr[cur]是0就把0放到dest和dest-1位置复写然后cur--dest - 2。三、代码实现Java代码很清晰看class Solution { public void duplicateZeros(int[] arr) { int cur 0, dest -1, n arr.length; // 1. 先找到最后一个需要复写的数 while (cur n) { if (arr[cur] 0) { dest 2; } else { dest 1; } if (dest n - 1) { break; } cur; } // 2. 处理边界情况比如最后一个元素是0复写后dest超了 if (dest n) { arr[n - 1] 0; cur--; dest - 2; } // 3. 从后向前完成复写操作 while (cur 0) { if (arr[cur] ! 0) { arr[dest--] arr[cur--]; } else { arr[dest--] 0; arr[dest--] 0; cur--; } } } }四、复杂度分析时间复杂度O(N)因为cur和dest都只遍历数组一次最多两次但总体是线性。空间复杂度O(1)就地修改没有额外空间。五、总结这道题的关键是双指针找位置从后往前填充。一开始可能会想新建数组但题目限制了就地修改所以用双指针先确定最后一个复写的数的位置再从后往前填避免了元素覆盖的问题。一定要手动模拟一遍过程就能理解cur和dest的移动逻辑啦~