导读

在阅读本文之前，推荐先读一下：
1. Remove Duplicates from Sorted Array

80. Remove Duplicates from Sorted Array II 题解

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],
Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.
It doesn’t matter what values are set beyond the returned length.

题解思路 双指针

如同LeetCode 26题Remove Duplicates from Sorted Array一样 ，给定一个排序数组，你需要在 “原地” 删除重复出现的元素，不同的是，本题要求使得每个元素最多出现两次，我们尝试用同样的套路来思考：
1. 选pivot，题目要求删除重复元素，那么要比较的pivot首先就是nums[0]，更新完第一个元素后就是nums[1]，以此类推
2. 确定遍历指针i的遍历范围，若数组的元素个数为n，遍历范围[l, r]应该是[2, n - 1]，因为每个元素最多出现两次，前两个就不用比较了
3. 确定待处理位置指针pos，pos设为第一个无效的位置，即 l - 1，这样 ++pos 后就是待处理的位置，那么pos应该初始化为1，同时，结合步骤1我们发现每步遍历的pivot其实就是nums[pos - 1]
4. 写一个类似 bool check(nums[i], pivot) 的函数，使其性质满足题目要求，题目要求元素不重复，就是 nums[i] != nums[pos - 1]
5. 写一个类似 oper(nums[++pos], nums[i]) 的函数，就是当check函数为true时，对待处理的 nums[++pos] 进行满足题意的操作，这里可以用覆盖操作，oper函数简化为 nums[++pos] = nums[i])

综上所述，我们不难写出代码：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2) return nums.size();

        int pos = 1;
        for (int i = 2; i < nums.size(); ++i) {
            if (nums[i] != nums[pos - 1]) nums[++pos] = nums[i];
        }

        return ++pos;
    }
};

套路还是可以用的，其实按这个套路我们可以把要求保留的元素个数推广到k个，示例代码：

class Solution {
public:    
    int removeDuplicates(vector<int>& nums, int k) {
        if (nums.size() <= k) return nums.size();

        int pos = k - 1;
        for (int i = k; i < nums.size(); ++i) {
            if (nums[i] != nums[pos - k + 1]) nums[++pos] = nums[i];
        }

        return ++pos;
    }
};