如何修复LeetCode 3Sum问题的Java代码以去除重复结果？

你的代码目前存在几个核心问题导致重复结果：

• 哈希表存储时，重复元素会覆盖之前的索引，导致无法正确匹配符合条件的元素
• 缺少补数索引的合法性判断，会出现重复使用当前i/j位置元素的情况
• 没有任何去重机制，相同的三元组会被多次添加

下面提供两种修复方案：

方案一：基于原哈希表思路修复 #

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> resultSet = new HashSet<>(); // 用Set去重
    Map<Integer, List<Integer>> numIndices = new HashMap<>();

    // 存储每个数值对应的所有索引
    for (int i = 0; i < nums.length; i++) {
        numIndices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
    }

    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int complement = -nums[i] - nums[j];
            if (numIndices.containsKey(complement)) {
                // 遍历补数的所有索引，找到大于j的索引（避免重复使用i/j的元素）
                for (int k : numIndices.get(complement)) {
                    if (k > j) {
                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], complement);
                        Collections.sort(triplet); // 排序后存入Set，确保相同组合被去重
                        resultSet.add(triplet);
                        break; // 找到一个符合条件的k即可，避免重复添加
                    }
                }
            }
        }
    }

    return new ArrayList<>(resultSet);
}

关键修复点： #

• 用HashMap<Integer, List<Integer>>存储每个数值的所有索引，避免覆盖
• 补数的索引必须大于j，保证三元组的元素位置合法（i<j<k）
• 用HashSet存储排序后的三元组，自动去重相同的组合

方案二：双指针法（更高效，推荐） #

哈希表法时间复杂度为O(n²)，但双指针法在排序后可以更高效地处理，同时天然容易去重：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // 先排序，方便去重和双指针移动

    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复的i，避免生成重复三元组
        if (i > 0 && nums[i] == nums[i-1]) {
            continue;
        }

        int left = i + 1;
        int right = nums.length - 1;
        int target = -nums[i];

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 跳过左侧重复元素
                while (left < right && nums[left] == nums[left+1]) {
                    left++;
                }
                // 跳过右侧重复元素
                while (left < right && nums[right] == nums[right-1]) {
                    right--;
                }
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

优势： #

• 排序后通过跳过相邻重复元素，直接避免生成重复三元组，无需额外Set去重
• 时间复杂度为O(n²)，但实际运行效率比哈希表法更高，因为减少了哈希操作的开销

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