For example, I am provided an array: 1, 3, 9, 6, 5, 8, 3, 4 The 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 parameter
int input[] = {1, 3, 9, 6, 5, 8, 3, 4};
我希望输出应该是:
[1, 8]
[3, 6]
[5, 4]
但是我的代码产生了不同的输出:
[1, 8]
[3, 6]
[6, 3]
[5, 4]
最佳答案
-----**更新以获得更好的解决方案**-----
如果您不介意数字成对的顺序,我建议您使用 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);
}
}
关于java - 在数组中查找加起来等于给定总和的非重复对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56437173/