Найдите все пары чисел в массиве, которые складываются в заданную сумму в Java

Автор оригинала: baeldung.

1. Обзор

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

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

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

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

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

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

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

При таком подходе наш алгоритм должен вернуться:

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

В каждом из алгоритмов, когда мы находим целевую пару чисел, которые суммируются с целевым числом, мы собираем эту пару с помощью служебного метода addPairs(i, j) .

Первый способ, которым мы могли бы подумать о реализации решения, – это использование традиционного для петля:

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

Это может быть немного рудиментарно, поэтому давайте также напишем реализацию с использованием API потока Java 8 .

Здесь мы используем метод IntStream.range для генерации последовательного потока чисел. Затем мы фильтруем их по нашему условию: число 1 + число :

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}

Если мы используем традиционную для петля, у нас будет:

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

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

Теперь давайте решим проблему с помощью Java 8 и Stream API:

Map 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. Заключение

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

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