27. 移除元素

力扣题目链接

这道题想让你实现删除数组里所有的某个值的元素，然后返回还剩下多少元素。

我按照自己的想法写了一个出来：

class Solution {
  public:
	int removeElement(vector<int> &nums, int val)
	{
		int len = nums.size();
		int i = 0, j = 0;
		for (j = 0; j < len; j++) {
			if (nums[j] != val) {
				nums[i] = nums[j];
				i++;
			}
		}
		return i;
	}
};

后面得知这正是数组删除元素使用的方法，也就是双指针法（快慢指针法）。

双指针法

删除元素，那就每次看到那个元素都把后面的所有往前移一次，把它覆盖掉？

不行，这个是$O(n^2)$,效果太差。

我们可以改用另外一种思路：我不去动这些要被删的元素，我去把不被删除的元素挑出来，重新构建一个数组。这正是双指针法。

双指针里面有2个指针，一快一慢，快的那个在一个个扫描原来数组的内容，慢的这个在一个个重建数组的新内容。由于新数组一定比旧数组元素少，慢指针一定不会超越快指针，使得不会有信息被慢指针的重建行为覆盖掉。

具体的逻辑是这样：快指针按顺序遍历每一个数组元素。发现等于删除元素，直接跳过；不等于删除元素，那就把元素复制到慢指针那里，然后慢指针往前移。最终慢指针指向的位置是新数组的后面一位，慢指针的数值刚刚好是剩下来元素的个数。