两数之和问题中如何去除结果集合里的重复元素？

问题描述 #

给定整数数组nums和整数target，返回两个数的索引，使它们的和等于target。当前代码可运行，但存在两个问题：

• 出现重复配对，比如(4,8)和(8,4)同时出现在结果中
• 出现逻辑错误的自配对，数组中仅存在一个6时，却生成了(6,6)的配对

原代码 #

//Class for pairs
public static class Pair{
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Pair() {
        }

        @Override
        public String toString() {
            return "{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }


//function that returns the pairs
public static ArrayList<Pair> twoSum(int[] arr, int target){
        ArrayList<Pair> result = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < arr.length;i++) {
            map.put(arr[i], i);
        }
        for (int j : arr) {
            if (map.containsKey(target - j)) {
                result.add(new Pair(j, arr[map.get(target - j)]));
            }
        }
        return result;
    }

示例输入与输出 #

• 输入：int arr[] = {1, 4, 3, 5, 6, 8}; int target = 12;
• 当前错误输出：[{x=4, y=8},{x=6, y=6}, {x=8, y=4}]

问题根源 #

1. 重复配对：遍历数组时，每个元素都会检查对应的补数，导致a找b和b找a都被加入结果。
2. 自配对错误：当元素的两倍等于target时，即使数组中只有一个该元素，map中存在该元素的索引，代码会直接生成自配对，没有检查是否是同一个位置的元素。
3. 偏离需求：原代码返回的是数值对而非索引对，既不符合题目要求，也增加了重复判断的难度。

修复后的代码 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class TwoSumSolution {
    // 存储索引对的类，统一索引顺序避免重复
    public static class Pair {
        int index1;
        int index2;

        public Pair(int index1, int index2) {
            // 固定小索引在前，大索引在后，确保配对唯一
            if (index1 < index2) {
                this.index1 = index1;
                this.index2 = index2;
            } else {
                this.index1 = index2;
                this.index2 = index1;
            }
        }

        @Override
        public String toString() {
            return "{" +
                    "index1=" + index1 +
                    ", index2=" + index2 +
                    '}';
        }

        // 重写equals和hashCode，让HashSet能识别重复配对
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return index1 == pair.index1 && index2 == pair.index2;
        }

        @Override
        public int hashCode() {
            return 31 * index1 + index2;
        }
    }

    public static ArrayList<Pair> twoSum(int[] arr, int target) {
        ArrayList<Pair> result = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Set<Pair> uniquePairs = new HashSet<>(); // 自动去重

        for (int i = 0; i < arr.length; i++) {
            int complement = target - arr[i];
            // 检查补数存在，且不是当前元素的索引（避免自配对）
            if (map.containsKey(complement)) {
                Pair pair = new Pair(map.get(complement), i);
                uniquePairs.add(pair);
            }
            // 先检查再存，避免刚存入的元素立即匹配到自己
            map.put(arr[i], i);
        }

        result.addAll(uniquePairs);
        return result;
    }

    // 测试示例
    public static void main(String[] args) {
        int arr[] = {1, 4, 3, 5, 6, 8};
        int target = 12;
        ArrayList<Pair> pairs = twoSum(arr, target);
        System.out.println(pairs); // 输出：[{index1=1, index2=5}]
    }
}

修复说明 #

1. 解决自配对问题：将元素存入map的操作放在补数检查之后，避免刚存入的元素立即被自己匹配到；同时确保补数的索引和当前索引不同，处理数组有重复元素的场景。
2. 去除重复配对：
   • 自定义Pair类时统一索引顺序（小索引在前），让(1,5)和(5,1)被视为同一对象。
   • 重写equals和hashCode方法，利用HashSet自动过滤重复配对。
3. 贴合需求：返回的是索引对而非数值对，完全符合题目“返回两个数的索引”的要求。

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