LeetCode/solutions/80. Remove Duplicates from Sorted Array II.md

80. Remove Duplicates from Sorted Array II

思路

要求去除有序数组中的重复元素，每个元素最多允许出现两次，要求不使用额外空间。
从前往后遍历数组，用len记录当前已去除重复元素后数组的元素个数，再用times记录当前已去除重复元素后数组的最后一个元素（即nums[len - 1]）的出现次数。则分成两种情况：

• 若当前元素不等于当前去除重复元素后的最后一个元素，即nums[i] != nums[len - 1]，说明当前元素不应该丢弃，则应该将times更新为1， 然后还要更新len及nums[len]；
• 否则，如果times == 1，说明之前才出现一次，则此次重复满足要求，则更新time为2，再更新len及nums[len]。

时间复杂度O(n), 空间复杂度O(1)

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int size = nums.size();
        if(size < 3) return size;
        int len = 1, times = 1;
        for(int i = 1; i < size; i++){
            if(nums[i] != nums[len - 1]) {
                times = 1;
                nums[len++] = nums[i];
            }
            else if(times == 1){
                nums[len++] = nums[i];
                times = 2;
            }
        }
        return len;
    }
};