双指针 | 移动零

本文主要是介绍双指针 | 移动零 | 复写零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.移动零

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

解题思路：

right指针一直往后移动，当nums[right]非0时和left指向的元素交换，然后left往后移动。
如果nums只有一个元素如[1]，那么直接交换没有影响，两外left变为1，没有访问数组是不会越界的。

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int left = 0,right = 0; right < nums.size();right++){if(nums[right] != 0){swap(nums[left],nums[right]);left++;}    }}
};

2.复写零

题目描述：

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

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

示例：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]

解题思路：

方法一：O(N^2)

使用index指针遍历，当index下标指向的元素是0将该位置往后的元素整体往后移动。腾出的那个位置填上0即可。
注意判断index刚好为最后一个且为0的特殊情况

class Solution {
public:void duplicateZeros(vector<int>& arr) {for(int index = 0;index < arr.size();index++){if(arr[index] == 0){for(int tmp = arr.size() -1;tmp > index;tmp--){arr[tmp] = arr[tmp-1];}if(index + 1 < arr.size()){arr[index+1] = 0;index++;}}}}
};

方法二：（O(N)）

方法一，当找到index下标指向的元素为0，然后从前往后移动元素，浪费时间。能不能从后往前移动？[快慢双指针]
当left下标的元素非0时right++，为0则right+=2。最终right指向最后一个位置，right和left恰好腾出来两个位置，为两个0插入增加空间。（这起始位置很巧妙）
特殊情况，left指向的位置由于空间不足，无法添加一个0，而且right也越界了。arr[arr.size() -1] = 0，right -=2，left–。
从后往前移动，当arr[left]非0，移动即可，arr[left]为了添加一个0

class Solution {
public:void duplicateZeros(vector<int>& arr) {int left = 0,right = -1;while(left < arr.size()){if(arr[left] != 0)right++;else right +=2;if(right >= arr.size() - 1)break;left++;}if(right == arr.size()){arr[arr.size() -1] = 0;left--;right-=2;}while(left >= 0){if(arr[left] != 0){arr[right] = arr[left];right--;}else{arr[right--] = 0;arr[right--] = 0;}left--;}}
};