Coding ManJava数组中查找的所有数字对，其总和等于给定数字
1. 概述
在这个快速教程中，我们将展示如何实现一种算法，以查找数组中的所有数字对，其总和等于给定数字。我们将集中讨论解决这个问题的两种方法。
在第一种方法中，无论唯一性如何，我们都会找到所有此类对。在第二个中，我们将只找到唯一的数字组合，删除冗余对。
对于每种方法，我们将展示两种实现——一种使用 for循环的传统实现，另一种使用 Java 8 Stream API。
2. 返回所有匹配的对
我们将遍历一个整数数组，使用蛮力、嵌套循环的方法找到总和为给定数字（sum ）的所有对（ i和 j ）。该算法将具有$$ O \left ( n^{2} \right ) $$的运行时复杂度。
对于我们的演示，我们将使用以下input数组查找总和等于6的所有数字对：
int[] input = { 2, 4, 3, 3 };
在这种方法中，我们的算法应该返回：
{2,4}, {4,2}, {3,3}, {3,3}
在每种算法中，当我们找到一个目标数对，总和等于目标数时，我们将使用实用方法*addPairs(i, j)*收集这对数。
我们可能认为实现解决方案的第一种方法是使用传统的 for 循环：
for (int i = 0; i < input.length; i++) {
for (int j = 0; j < input.length; j++) {
if (j != i && (input[i] + input[j]) == sum) {
addPairs(input[i], sum-input[i]));
}
}
}
这可能有点初级，所以让我们也使用 Java 8 Stream API 编写一个实现。
在这里，我们使用方法 IntStream.range来生成顺序的数字流。然后，我们根据我们的条件过滤它们：数字 1 + 数字 2 = sum：
IntStream.range(0, input.length)
.forEach(i -> IntStream.range(0, input.length)
.filter(j -> i != j && input[i] + input[j] == sum)
.forEach(j -> addPairs(input[i], input[j]))
);
3. 返回所有唯一的匹配对
对于这个例子，我们必须开发一个更智能的算法，它只返回唯一的数字组合，省略冗余对。
为了实现这一点，我们将每个元素添加到哈希映射（不排序），首先检查该对是否已经显示。如果没有，我们将检索并标记它，如图所示（将值字段设置为null）。
因此，使用与之前相同的input数组，目标总和为6，我们的算法应该只返回不同的数字组合：
{2,4}, {3,3}
如果我们使用传统的 for循环，我们将拥有：
Map<Integer, Integer> pairs = new HashMap();
for (int i : input) {
if (pairs.containsKey(i)) {
if (pairs.get(i) != null) {
addPairs(i, sum-i);
}
pairs.put(sum - i, null);
} else if (!pairs.containsValue(i)) {
pairs.put(sum-i, i);
}
}
请注意，此实现改进了以前的复杂性，因为我们只使用一个 for循环，所以我们将有$$ O \left ( n \right ) $$ 。
现在让我们使用 Java 8 和 Stream API 来解决这个问题：
Map<Integer, Integer> pairs = new HashMap();
IntStream.range(0, input.length).forEach(i -> {
if (pairs.containsKey(input[i])) {
if (pairs.get(input[i]) != null) {
addPairs(input[i], sum - input[i]);
}
pairs.put(sum - input[i], null);
} else if (!pairs.containsValue(input[i])) {
pairs.put(sum - input[i], input[i]);
}
});