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 <= 104
• 0 <= arr[i] <= 9

---

解题分析及思路：

方法：双指针

思路：

利用双指针的思路，快慢指针从下标0开始，往后进行遍历，在慢指针遇到0时，快指针多走一步，最终会得到两个快慢指针：left（慢指针）、right（快指针）

例如：1,0,2,3,0,4,5,0，在两个指针走完之后，慢指针位于下标7，快指针位于下标10（已越界，代表超出原数组3个元素）

然后采用逆思路，将快慢指针按照原来的步伐重新走回去赋值即可。

也就是快慢指针以现有位置，往前进行遍历，当慢指针遇到0时，给快指针所在位置赋值后，快指针需要再走一步，再次赋值。

注意：当快指针超出数组范围时，忽略赋值，往前移动指针即可（即快指针位于下标8 - 10时）。

func duplicateZeros(arr []int) {
  // 获取快慢指针
	var left, right = -1, -1
	for index := range arr {
		if arr[index] == 0 {
			right++
		}
		left++
		right++
	}
  // 重新赋值
	for left >= 0 {
		if right < len(arr) {
			arr[right] = arr[left]
		}
		right--
		if arr[left] == 0 {
			if right < len(arr) {
				arr[right] = arr[left]
			}
			right--
		}
		left--
	}
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:4 ms,击败了50.00% 的Go用户
• 内存消耗:3.4 MB,击败了100.00% 的Go用户