java - 在数组中查找加起来等于给定总和的非重复对

Question

For example, I am provided an array: 1, 3, 9, 6, 5, 8, 3, 4The problem is that I have to find pairs whose sum is 9 in the array mentioned above. However, the pair must not be repetitive. This means if I already found the first pair [3, 6], then the second pair [6, 3] is not accepted.

The output of this problem should be [1, 8] [3, 6] [5, 4] (no [6, 3] because it is repetitive)

I use Java 8 to solve this problem.

Here are some codes that I tried:

public static void printSumNine(int[] input)
{
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                System.out.println("[" + input[i] + ", " + input[j] + "]");
            }
        }
    }
}

Then I put this input in the parameterint input[] = {1, 3, 9, 6, 5, 8, 3, 4};

我希望输出应该是:

[1, 8] 
[3, 6]
[5, 4]

但是我的代码产生了不同的输出:

[1, 8]
[3, 6]
[6, 3]
[5, 4]

Answer 1

-----**更新以获得更好的解决方案**-----

如果您不介意数字成对的顺序，我建议您使用 Set并且它只需要 O(N) 就可以比当前解决方案中的 O(NlogN) 更好地完成您的任务。

解决方案:

    int N = 9;
    Set<Integer> set = new HashSet<>();
    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };

    for (int i = 0; i < input.length; i++) {
        //condition N = input[i] * 2 is for some cases such as (N = 8, and array contains 2 numbers which have same value 4)
        if (set.contains(N - input[i]) && (!set.contains(input[i]) || (N ==input[i] *2)) {
            System.out.println(input[i] + " - " + (9 - input[i]));
        }
        set.add(input[i]);
    }

Hashset.contains 的复杂度为 O(1)，而您只需运行 1 个循环即可解决您的问题。

---

我建议使用 Map删除重复项。

Map<Integer, Integer> usedMap

这是我修改后的版本。尽管它的复杂性不好，但它是可行的。如果我能找到另一个更复杂的方法，我将编辑这篇文章。

    Map<Integer, Integer> usedMap = new HashMap<Integer, Integer>();

    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };
    for (int i = 0; i < input.length - 1; i++) {
        if (!usedMap.containsKey(input[i])) {
            for (int j = i + 1; j < input.length; j++) {
                if (!usedMap.containsKey(input[j])) {
                    if (9 - input[i] == input[j]) {
                        System.out.println("[" + input[i] + ", " + input[j] + "]");
                        usedMap.put(input[j], 1);
                    }
                }
            }
            usedMap.put(input[i], 1);
        }

    }