使用HashSet解决有序数组去重问题遇错求助

你的代码出现问题的核心原因很明确：你只统计了不重复元素的数量，但完全没有原地修改原数组nums。题目要求你在原数组上把不重复的元素放到数组的前半部分，而你的代码只是把元素丢进HashSet里就结束了，原数组的内容还是输入时的[1,1,2]，所以评测系统检查数组前2位（你返回的长度）时，自然会得到[1,1]，和预期不符。

而且还要注意，题目要求使用常量内存，HashSet的空间复杂度是O(n)，其实已经不符合这个要求了。更关键的是，因为输入数组是有序的，我们根本不需要用HashSet这种额外空间的方法，双指针法才是最优解，既满足常量内存，又能高效完成原地修改。

正确的双指针解法 #

思路很简单：用两个指针，一个慢指针标记当前已处理的不重复元素的最后位置，另一个快指针遍历整个数组，遇到不重复的元素就更新慢指针的位置并赋值：

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        // slow指针指向最后一个不重复元素的位置
        int slow = 0;
        // fast指针遍历整个数组
        for (int fast = 1; fast < nums.length; fast++) {
            // 遇到和slow位置不同的元素，说明是新的不重复元素
            if (nums[fast] != nums[slow]) {
                slow++;
                // 把新元素放到slow的新位置
                nums[slow] = nums[fast];
            }
        }
        // 新长度是slow+1（因为slow从0开始计数）
        return slow + 1;
    }
}

针对输入[1,1,2]的执行过程： #

1. 初始slow=0，fast=1：nums[1]等于nums[0]（都是1），跳过；
2. fast=2：nums[2]是2，不等于nums[0]，slow变为1，把nums[2]的值赋给nums[1]，此时数组变成[1,2,2]；
3. 循环结束，返回slow+1=2，数组前两位正好是[1,2]，完全符合预期。

为什么你的HashSet方法不可行？ #

就算你非要用HashSet，你也需要把Set里的元素重新写回原数组的前几位，但这里有两个问题：

• 普通HashSet是无序的，会破坏原数组的有序性（题目虽然没明确说要保持顺序，但输入是有序的，预期输出也是有序的，所以应该保持）；
• HashSet占用了额外的O(n)空间，不符合题目要求的常量内存限制。

所以双指针法才是这个问题的标准解法。

内容的提问来源于stack exchange，提问作者Alice