1. Overview

1.概述

In this quick tutorial, we’ll show how to implement an algorithm for finding all pairs of numbers in an array whose sum equals a given number. We’ll focus on two approaches to the problem.

在这个快速教程中，我们将展示如何实现一种算法，以寻找数组中总和等于给定数字的所有数字对。我们将重点介绍解决该问题的两种方法。

In the first approach, we’ll find all such pairs regardless of uniqueness. In the second, we’ll find only the unique number combinations, removing redundant pairs.

在第一种方法中，我们将找到所有这样的数字对，不管是否唯一。在第二种方法中，我们将只找到唯一的数字组合，去除多余的配对。

For each approach, we’ll present two implementations — a traditional implementation using for loops, and a second using the Java 8 Stream API.

对于每一种方法，我们将介绍两种实现方式–一种是使用for 循环的传统实现，另一种是使用Java 8 Stream API的实现。

2. Return All Matching Pairs

2.返回所有匹配的对子

We’ll iterate through an array of integers, finding all pairs (i and j) that sum up to the given number (sum) using a brute-force, nested-loop approach. This algorithm will have a runtime complexity of O(n²).

我们将遍历一个整数数组，使用粗暴的、嵌套的循环方法找到所有对(i和j)，其总和等于给定的数字(sum)。该算法的运行时间复杂度为O(n²)。

For our demonstrations, we’ll look for all pairs of numbers whose sum is equal to 6, using the following input array:

在我们的演示中，我们将使用下面的input数组，寻找所有和等于6的数对。

int[] input = { 2, 4, 3, 3 };

In this approach, our algorithm should return:

在这种方法中，我们的算法应该返回。

{2,4}, {4,2}, {3,3}, {3,3}

In each of the algorithms, when we find a target pair of numbers that sum up to the target number, we’ll collect the pair using a utility method, addPairs(i, j).

在每一种算法中，当我们发现一对目标数字的总和为目标数字时，我们将使用一个实用方法收集这对数字，addPairs(i, j)。

The first way we might think to implement the solution is by using the traditional for loop:

我们可能认为实现解决方案的第一种方式是使用传统的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]));
        }
    }
}

This can be a bit rudimentary, so let’s also write an implementation using the Java 8 Stream API.

这可能有点简陋，所以让我们也用Java 8 Stream API写一个实现。

Here, we use the method IntStream.range to generate a sequential stream of numbers. Then, we filter them for our condition: number 1 + number 2 = sum:

这里，我们使用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. Return All Unique Matching Pairs

3.返回所有独特的匹配对

For this example, we’ll have to develop a smarter algorithm that returns only the unique number combinations, omitting redundant pairs.

对于这个例子，我们必须开发一个更聪明的算法，只返回唯一的数字组合，省略多余的配对。

To achieve this, we’ll add every element to a hash map (without sorting), checking first if the pair has already been shown. If not, we’ll retrieve and mark it as shown (set value field as null).

为了实现这一目标，我们将把每个元素添加到哈希图中（不进行排序），首先检查该对元素是否已经被显示。如果没有，我们将检索并标记为已显示（将value字段设置为null）。

Accordingly, using the same input array as before, and a target sum of 6, our algorithm should return only the different number combinations:

因此，使用与之前相同的输入数组，并且目标和为6，我们的算法应该只返回不同的数字组合。

{2,4}, {3,3}

If we use a traditional for loop, we’ll have:

如果我们使用一个传统的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);
    }
}

Note that this implementation improves on the previous complexity, as we use only one for loop, so we’ll have O(n).

请注意，这个实现比之前的复杂度有所提高，因为我们只使用一个for循环，所以我们会有O(n)。

Now let’s solve the problem using Java 8 and the Stream API:

现在让我们用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]);
    }
});

4. Conclusion

4.结论

In this article, we explained several different ways to find all pairs that sum up a given number in Java. We saw two different solutions, each using two Java core methods.

在这篇文章中，我们解释了在Java中寻找所有与给定数字相加的对的几种不同方法。我们看到了两种不同的解决方案，分别使用两种Java核心方法。

As usual, all the code samples shown in this article can be found on GitHub — this is a Maven project, so it should be easy to compile and run it.

像往常一样，本文展示的所有代码样本都可以在GitHub上找到–这是一个Maven项目，所以编译和运行它应该很容易。