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

26.删除有序数组中的重复项

给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解决思路

背景：有序数组，重复元素，原地算法。

目标：删除重复元素，返回新数组长度。

方法：使用快慢指针。

比如下面的数组，我们希望能尽快的找到两个不同的元素并将不同的元素放到合适的位置，这样就可以将重复的元素折叠起来，达到我们删除重复元素的目的。

nums = [0,0,1,1,1,2,2,3,3,4]

快慢指针 或许可以达到我们的要求。

快指针不断地寻找与慢指针不同的元素，找到的话将其放到慢指针后面的位置，之后再寻找下一个相异的元素；若没找到的话，仅需要向右移动快指针就好了。

让我们来看看具体情况。

             fast
             |
1. nums = [0,1,1,1,2,2,3,3,4]
           |
           slow

如1.所示，在这种情况下，快慢指针指向的元素互异，此时要将fast指向的元素移动到slow后面的位置，之后要移动两个指针的位置，将他们指向各自的下一个元素，之后再进行下一次比较。此时的情况如2.所示。

               fast
               |
2. nums = [0,1,1,1,2,2,3,3,4]
             |
             slow

在2.这种情况下，快慢指针指向的元素相同，此时只移动快指针，直到变成3.这种情况。

                   fast
                   |
3. nums = [0,1,1,1,2,2,3,3,4]
             |
             slow

此时快慢指针所指的元素互异，将fast指向的元素移动到slow后面的位置。如4.所示，元素和指针都发生了移动，此时的结果是我们预想中的结果。

                     fast
                     |
3. nums = [0,1,2,1,2,2,3,3,4]
               |
               slow

那么我们的操作到何时结束呢？4.显示了结束时快慢指针的状态，快指针遍历完最后一个元素，此时慢指针及之前的元素都是我们需要的去除掉重复元素之后的部分，该部分的长度为slow + 1。

                            fast
                            |
4. nums = [0,1,2,3,4,2,3,3,4]
                   |
                   slow

不过我们还需要考虑边界情况，即当数组元素小于2时肯定不会出现重复元素，此时我们直接返回原数组长度即可。

能够通过的代码如下：

#include <vector>

using namespace std;

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