«1. Обзор

В этом кратком руководстве мы покажем, как реализовать алгоритм поиска всех пар чисел в массиве, сумма которых равна заданному числу. Мы сосредоточимся на двух подходах к проблеме.

В первом подходе мы найдем все такие пары независимо от их уникальности. Во втором мы найдем только уникальные комбинации чисел, удалив лишние пары.

Для каждого подхода мы представим две реализации — традиционную реализацию с использованием циклов for и вторую с использованием Java 8 Stream API.

2. Вернуть все совпадающие пары

Мы пройдемся по массиву целых чисел и найдем все пары (i и j), которые в сумме дают заданное число (сумму), используя подход грубой силы с вложенным циклом. . Этот алгоритм будет иметь сложность времени выполнения O (n2).

Для наших демонстраций мы будем искать все пары чисел, сумма которых равна 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 = сумма: 

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. Возвращаем все уникальные совпадающие пары

Для этого примера нам придется разработать более умный алгоритм, который возвращает только уникальные комбинации чисел , опуская лишние пары.

Для этого мы добавим каждый элемент в хеш-карту (без сортировки), предварительно проверив, была ли уже показана пара. Если нет, мы получим и пометим его, как показано (установите поле значения как нулевое).

Соответственно, используя тот же входной массив, что и раньше, и целевую сумму 6, наш алгоритм должен возвращать только различные комбинации чисел: 

{2,4}, {3,3}

Если мы используем традиционный цикл for, мы получим: ~ ~~ Обратите внимание, что эта реализация улучшает предыдущую сложность, так как мы используем только один цикл for, поэтому у нас будет O(n). 

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);
    }
}

Теперь давайте решим задачу, используя Java 8 и Stream API:

4. Заключение 

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]);
    }
});

В этой статье мы объяснили несколько различных способов поиска всех пар, суммирующих заданное число в Java. Мы видели два разных решения, каждое из которых использует два основных метода Java.

Как обычно, все примеры кода, показанные в этой статье, можно найти на GitHub — это проект Maven, поэтому его легко скомпилировать и запустить.

«