https://leetcode-cn.com/problems/remove-element/
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

我的方法一：快慢双指针

步骤

1. slow慢指针表示去重之后的数组的最后一位
2. fast快指针表示要检查的是否等于val的那一位
3. 判断fast是否是val
   3.1 如果不是，将fast的值设置给slow+1的位置；并将fast和slow都右移一位
   3.2 如果是，fast右移一位，slow不动
4. 直到fast遍历完了所有的位
5. 由于slow表示去重之后的最后一位，所以slow+1表示去重后的长度

初始条件

1. slow=-1， 因为slow表示去重之后的最后一位，初始时去重的长度是0，所以位数是-1
2. fast=0，因为表示要检查的第一位，所以是0

边界条件

1. fast<nums的长度

复杂度

时间：O(n)，fast遍历了一遍
空间：O(1)

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = -1;
        int fast = 0;
        int n = nums.size();

        while(fast < n) {
            if(nums[fast] != val) {
                nums[++slow] = nums[fast];
            }
            fast++;
        }

        return ++slow;
    }
};

我的方法二：左右双指针，【稍微有些绕版本】

快慢双指针的缺点是，如果存在val，那么val之后的所有的数都会左移，所以一个最差的情况，第一位是val，其余都不是，那么方法一会将所有的数都左移一位，其实将最后一个数设置给第0位即可。
该方法就是做这个优化的。

步骤

1. left和right分别表示下一个要判断是否val的位数和去除后的最后一位
2. 先判断left是否是val，如果不是那么右移left，如果是，那么将right的给left，然后right左移一位

初始条件

1. left=0，因为0表示下一个要判断的位数
2. right=nums.size()-1，因为nums.size()-1表示初始状态下数组nums的最后一位

边界条件

left<=right，为什么不是left<right？，因为left是下一个要判断的位数，所以有可能left就是指向right，所以应该包括等号。有些绕，看方法三，稍微改变一点思路，代码逻辑就清楚很多

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size() == 0) {
            return 0;
        }

        int left = 0;
        int right = nums.size() - 1;

        while(left <= right) {
            if(nums[left] == val) {
                nums[left] = nums[right];
                right--;
            }else{
                left++;
            }
        }

        return left;
    }
};

我的方法三：左右双指针，【比方法二逻辑更清晰版】

步骤

1. left是左指针，表示要判断是否val的位数
2. n是右指针，但是n表示去除了val之后的有效长度
3. 判断left是否是val
   3.1 如果不是，那么右移left；
   3.2 如果是，那么将数组最后一位设置给left，注意不右移left，因为有可能设置的新值也是val；n--表示去除一个val后，长度减1；

初始条件

1. 由于left表示要判断是否val的位数，所以是0
2. 由于n表示去除val之后的长度，所以初始是nums.size()-1

边界条件

1. left<n，不需要等号，因为left=n就越界了，所以这个逻辑比方法二要清晰很多

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size() == 0) {
            return 0;
        }

        int left = 0;
        int n = nums.size();

        while(left < n) {
            if(nums[left] == val) {
                nums[left] = nums[--n];
            }else{
                left++;
            }
        }

        return n;
    }
};