题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝。
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
题解
方法一：双指针
刚刚拿到这道题，很多朋友第一反应就是用循环嵌套去遍历数组，遇到等于val的元素就把后面的元素依次向前移动一个。但是这样考虑会发现边界问题不好处理，而且效率极其低下。
不妨考虑使用双指针来解决这个问题。由于题目要求删除数组中等于 val的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。右指针 right 指向当前将要处理的元素，左指针 left指向下一个将要赋值的位置。如果右侧指针指向的元素不等于val，就把这个元素复制到左指针指向的位置，同时将左右指针都移动至下一位；若右指针指向的元素等于val，那么我们需要将其移除，方法是不去理会这个元素，左指针的位置不动，右指针直接移动至下一位。
这个算法就类似于一台打印机。右指针是一个扫描头，扫描容器中的每一个元素，将所有不等于val的元素报告给左指针，左指针相当于一个输出器，每得到并写下一个元素后就会向右移动一位，等待下一次输出。因此，左右指针遍历完输入数组以后，left的值就是要输出的数组的长度。结合代码来看看：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
};
通过代码很直观的即可看出这个算法的运作方式。方法一到此为止。
方法二：优化双指针
方法一看似已经十分巧妙的解决了问题，那么还有没有更好的优化方式呢？从空间复杂度来看，我们已经只是在原地修改元素，没有使用其他空间，是行不通的了，那么，在方法一中，我们的左右两个指针你追我赶的出发，最坏情况下总共需要遍历整个数组两次，看来还是有改进的空间的。
首先想到，需要保留的元素可以不用重复赋值，我们只需要把不需要的元素，即，值与val相等的元素剔除出我们的数组即可。因此，我们采取一个左右指针分别从数组的两端开始移动的方法，如果左指针指向的元素值等于val，就将右指针指向的元素复制到左指针的位置，然后将右指针左移一位。如果赋值过来的元素恰好还是val，那么可以继续移动右指针进行复制，val值就会被继续覆盖，直到左指针的元素值不等于val为止。当左右两个指针重合的时候，左右指针遍历完数组中的所有元素。
很容易理解，看看代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};
这里改为使用了while循环，因为我们更容易判断出循环需要结束的条件，即左右指针相遇。而之前使用的for循环更适合在我们知道循环需要进行的次数边界时进行使用。要注意，因为有第0元素的存在，right指针需要在最开始就减去1。
至此，方法二就到这里了。
写在最后
不难看出，双指针是一种很巧妙很实用的解题方法，合理运用好双指针的操作，对于数组元素一类的题型能够更加轻松的解决。
