力扣27.移除元素

简单

解题思路

简单来说，就是根据提供的数组，查找与 val 不相同的值，在原数组上整理出一个新的有效部分。

在 vector 中提到删除，一下就想到了 erase，但这道题的正确解法应该是双指针。

vector 要求数组中元素地址是连续的，所以 erase 的清除实际上是覆盖。比如 erase(nums.begin()+2)，这个位置后面的元素会不断向前覆盖上去，实际上时间复杂度是 O (n)。

回到题目，要求更改 nums 数组，所以在 nums 本身上操作就可以，使用两个指针：左指针 left 和右指针 right（快慢指针）。

• 左指针 left：指向真正需要的数组元素的末尾（左闭右开区间，严格来说是真正的数组元素的末尾的下一个位置）。
• 右指针 right：用来在原本的 nums 中查找不等于 val 的元素。

初始时 left 和 right 都为 0：

• 当 right 指向的元素不等于 val 时（nums[right] != val），这是我们所需要的元素，将其放到 left 所指向的位置上（nums[left] = nums[right]），然后 left++，left 继续指向真正需要的数组元素的末尾的下一个地址。
• 当 right 指向的元素等于 val 时，直接 right++，跳过这个元素。

这样，nums 前面开始放的都是我们所需要的元素。那些等于 val 的元素，会被后面的有效元素覆盖掉。题目说了，返回的 k 个元素之外留下了什么并不重要，所以不用关心后面的元素怎样，只要前 k 个元素中没有等于 val 的值就行。

最后 k 值刚好等于真正需要的元素的个数，直接返回。该算法时间复杂度为 O (n)。