1. 题目

2. 解题思路

• 让 index指向删除重复元素后数组的新长度；
• 让 st_idx 指向重复元素的起始位置，而 i 指向重复元素的结束位置，duplicate_num代表重复元素的个数；
• 一段重复元素结束后，这时候如果 st_idx = index，那么无需搬移数据，只让 index 前进最多 2 个位置即可，如上面上图到右图的过程所示；
• 如果 st_idx != index，我们需要从 st_idx 开始最多搬移 2 个数据到 index 位置，如上面右图到左图的过程所示；
• 此时，如果 i 指向最后一个元素，那么直接将最后一个元素搬移到 index 位置，直接返回；
• 如果 i 还没有到最后一个元素，那么继续重复寻找下一段重复元素；

3. 代码实现

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:

        if len(nums) < 3:
            return len(nums)
        index = 0
        st_idx = 0
        duplicate_num = 1
        i = 1
        target = nums[0]
        while i < len(nums):
            while i < len(nums) and nums[i] == target:
                duplicate_num += 1
                i += 1
            
            if st_idx != index:
                for j in range(st_idx, st_idx+min(duplicate_num, 2)):
                    nums[index] = nums[st_idx]
                    st_idx += 1
                    index += 1
            else:
                index += min(2, duplicate_num)

            if i == len(nums) - 1:
                nums[index] = nums[i]
                index += 1
                return index
            if i < len(nums):
                st_idx = i
                target = nums[i]
                duplicate_num = 1
                i += 1

        return index

时间复杂度为 $O(n)$，最多遍历 2 遍数组，空间复杂度为 $O(1)$。

当然了，上面的思路不容易理清，比较简单的一个实现是利用快慢指针。一开始快慢指针都指向第 3 个元素，如果 nums[fast] = nums[slow-2]，说明重复元素超过了 2 个，只需要向前移动 fast 指针即可；如果 nums[fast] != nums[slow-2]，那么把 fast 指针指向的元素移动到slow 指针，二者都前进一步。最后，slow指针指向的位置即为结果所求。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

        if (nums.size() < 3)
            return nums.size();
        int slow = 2;
        int fast = 2;
        while (fast < nums.size()) {
            if (nums[fast] == nums[slow-2]) {
                fast++;
            } else {
                nums[slow++] = nums[fast++];
            }
        }
        return slow;
    }
};