算法学习：数组 - 双指针法

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

背景：数组

目的：删除数组中值为val的元素，并返回新数组长度。

方法：快慢指针

解题思路

这种删除并不是真正的删除，仅仅是挪动了元素的位置。

我们可以使用快慢指针，将我们需要的元素转移到数组左侧，或者将我们不需要的元素转移到数组的末尾。

将不需要的元素转移到数组末尾这件事比较容易。

我们将slow指针放到数组的末尾，并且保证slow位置以后的元素都是要删除的元素，如果fast发现了一个要删除的元素，那么就将该元素移动至slow的身后，具体应该如何去做呢？

这里也可以换一种说法：slow身后没有需要保留的元素。

我认为这种说法更不容易被误解。

初始状态，我们将两个指针均置于数组末尾。

比较fast所指的元素是否为val，如果是的话，交换俩指针所指的元素并将两指针左移一个位置；如果不是则将fast左移，查看下一个元素。

你可能会产生疑问，如果slow和fast同时指向值为val的元素要怎么处理，那么我们来看下面的几种情况。

				  fast
				  | 
nums = [1,2,3,2,3,3]; val = 3; 
                  |
                  slow

上面是第一种情况，两指针同时指向值为val的元素。按照我们上面说的处理办法，将两指针元素交换同时左移一个位置，结果如下：

				fast
				| 
nums = [1,2,3,2,3,3]; val = 3; 
                |
                slow

此时又满足上述情况，于是继续处理，结果如下：

	          fast
		      | 
nums = [1,2,3,2,3,3]; val = 3; 
              |
              slow

此时我们保证了slow身后没有需要保留的元素，而fast要继续寻找，直到找到全部的被删除的元素，最终数组元素以及两指针的位置应该是这样的：

	   fast
	   | 
nums = [1,2,2,3,3,3]; val = 3; 
            |
            slow

最终我们需要的数组长度为slow + 1。

你也许会考虑这样的情况：

			fast
			| 
nums = [1,2,3,2,3,3]; val = 3; 
                |
                slow

这样的情况真的会出现么？如果使用了上述的策略，必然不会出现这样的情况，因为我们已经做到了对于slow的保证。

我们再来考虑一种极端的情况：

nums = [3,3,3]; val = 3; 

这种情况下，两指针会一起移动到下标为-1的位置，同时返回0这个结果，当然符合我们的预期。

数组元素为空的极端情况也是需要考虑的，若数组内无元素，在指针初始化时即指向-1的位置，最终返回0，依然符合预期。

代码如下：

#include <vector>

using namespace std;

class Solution
{
public:
    int removeElement(vector<int> &nums, int val)
    {
        int length = nums.size();
        int slow = length - 1;
        int fast = length - 1;
        while (fast >= 0)
        {
            if (nums[fast] == val)
            {
                std::swap(nums[fast], nums[slow--]);
            }
            --fast;
        }
        return slow + 1;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    vector<int> nums = {1, 1, 2};
    s.removeElement(nums, 1);
    return 0;
}