双指针 | 移动零 | 复写零

1.移动零

题目描述：

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

示例：

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

解题思路：

1. right指针一直往后移动，当nums[right]非0时和left指向的元素交换，然后left往后移动。
   

2. 如果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)

1. 使用index指针遍历，当index下标指向的元素是0将该位置往后的元素整体往后移动。腾出的那个位置填上0即可。
   
2. 注意判断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)）

1. 方法一，当找到index下标指向的元素为0，然后从前往后移动元素，浪费时间。能不能从后往前移动？[快慢双指针]

2. 当left下标的元素非0时right++，为0则right+=2。最终right指向最后一个位置，right和left恰好腾出来两个位置，为两个0插入增加空间。（这起始位置很巧妙）
   

3. 特殊情况，left指向的位置由于空间不足，无法添加一个0，而且right也越界了。arr[arr.size() -1] = 0，right -=2，left–。

   

4. 从后往前移动，当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--;
        }
    }
};