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

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

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

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

我们也可以探究一个普遍解法，使每个元素最多出现K次。

背景：数组

目的：删除重复元素，每个元素最多出现K次

方法：快慢指针

解题思路

每个元素最多出现K次，那么数组中前K个元素一定是满足题意的元素，那么我们只需要关注K之后的元素就可以了。

将第N个元素与第N - K个元素比较，如果二者不同，那么就保留这个位置，如果二者相同，那么就将后面与之不同的元素放到该位置。

为何与第N - K个元素进行比较呢？原因在于最多出现K次这个条件，如果与第N - K个元素相同，说明该元素已经出现了K次，那么第N个位置就需要放入不同的元素。

我们来看看代码：

#include <vector>
using namespace std;

class Solution {
public:
    int removeDuplicates(vector<int>& nums,int k) {
        int length = nums.size();
        if (length <= 2)
        {
            return length;
        }
        int slow = k;
        int fast = k;
        while (fast < length)
        {
            if(nums[fast] != nums[slow - k]){
                nums[slow++] = nums[fast];
            }
            ++fast;
        }
        return slow + k;
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    vector<int> nums = {1,1,1,1,2,3,4,5};
    s.removeDuplicates(nums,2);
    return 0;
}