一道双指针问题

• 14 February 2018

Remove Duplicates from Sorted Array 是一道经典的双指针题目，要求移除有序数组中的重复元素。它的 follow up 是 Remove Duplicates from Sorted Array II，要求最多保留两个重复元素。后序变种还有最多保留三个重复元素怎么做，但是思路都是一样的。在网上看到不少解，觉得有的写的比较乱。下面是我总结的通用解法。

定义两个变量，i 和 j。i 代表隔板位置，i 以及 i 左侧表示所有满足条件的元素；j 代表当前坐标位置，它遍历一遍整个数组，因此最后有效数组在 =[0, i] 范围内。

只保留一个元素的解法：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (i == 0 || nums[j] != nums[i - 1]) {
                nums[i++] = nums[j];
            } 
        }
        return i;
    }
}

保留最多两个重复元素的解法：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (i == 0 || i == 1 || nums[j] != nums[i - 2]) {
                nums[i++] = nums[j];
            } 
        }
        return i;
    }
}

可以发现两道题的解法几乎是完全一样的。这里，判断重复元素的标准是 nums[j] 和 nums[i - k] 是否相等（k 表示保留几位重复元素）。

补充：一开始我在解只保留一个元素这道题的时候，大概思路是每次循环比较 nums[j] 和 nums[j - 1] 是否相等。这么写是能够 AC 的，但是这个思路只能跑通因为只保留一个元素的特殊情况，不是通用解法。用这个思路做保留两个元素的题目，结果就会报错。原因是因为可行解其实都在 i 和 i 的左侧，比较相邻的 j 是无法达到判断是否重复的效果的。如果还是想用这个思路做保留两个及多个元素的题目，需要再加一个计数器。