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

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

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

思路

基本思想

本题与 26.删除有序数组中的重复项 有些类似，只不过每种类型的元素不是只保留一个，而是最多保留两个，这个要求包含两层意思，第一个意思是本来就只出现一次或者两次的数据直接留下不删除，出现三次以上的数据需要删除多余的，只保留两次

这种从数组中删除不符合要求元素的题目，一般使用快慢指针来解题，需要明确的是，慢指针在题中代表的含义是当前需要保留的元素的最后位置。对于本题来说，当元素出现次数小于等于两次时就可以留下，如何使用代码表示当前元素出现次数小于等于两次呢？

可以考虑极端情况，当前元素是第三次出现，那么说明前两次已经保存起来了，现在slow慢指针指向的位置就是这个第三次出现的位置，当前元素不能保留，也就是当nums[fast]==nums[slow-2]的时候，这个元素不能保留，-2的原因是因为当前的元素需要保留最多两个，当前slow的位置前面有两个重复的元素时，当前slow的位置就可以覆盖，否则就不能覆盖

最开始的想法是，当当前元素出现第一次或者出现第二次时，都可以留下，判断的条件是：

1

nums[fast]!=nums[fast-1]||nums[fast]!=nums[fast-2]

但是当nums=[1,1,1,2,2,3]时，第一个2保留之后，nums变为[1,1,2,2,2,3]，此时slow在加粗的位置，fast在斜体的位置，使用上面的判断条件，fast处的元素无法保留，其实按照题意应该保留

使用nums[fast]!=nums[slow-2]这个条件时，一定能确保slow前面每种元素最多可以保留两个

核心就是明白slow代表当前需要保留的元素的最后的位置，fast是当前第一个待判断的元素

此处补充一下 26. 删除有序数组中的重复项 的解题思路，为了将每种元素保留一次，相当于每一种元素头一次出现时就需要记录一下，所以判断条件是nums[fast]!=nums[fast-1]就需要保留当前元素

执行流程

1. 从第三个元素开始，判断每个元素是否应该保留

2. 如果当前这种元素已经保留了两个了，那么就不需要再保留了

3. 如果当前元素还没有保留够两个，就尝试保留，没有够两个有两种情况：

   1. 当前元素第一次出现，需要保留
   2. 当前元素第二次出现，需要保留

   判断当前元素是否保留够两个的条件是看slow之前有没有两个当前元素，只要不够两个元素就可以保留

4. 返回有效元素的长度

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow=2,fast=2;
        while(fast<nums.length){
            //每一种元素最多保留两个
            //所以每一个元素都要与上一种元素进行比较，不同才留下来
            if(nums[fast]!=nums[slow-2]){
                nums[slow++]=nums[fast++];
            }else{
                fast++;
            }
        }
        return slow;
    }
}

总结

总结起来需要注意两点：

1. slow代表的是当前以保存的所有元素的最后位置
2. 每种元素最多可以保留两个

判断当前元素是否需要保留就是看slow前有没有两个以上的当前元素，也就是看slow退后两个位置处的元素与当前元素是否相等，不相等代表当前元素的出现次数少于2，可以保留，相等代表当前元素的出现次数大于2，不能保留，所以核心就是看**nums[fast]和nums[slow-2]**的关系