1. Обзор
В этом кратком руководстве мы покажем, как реализовать алгоритм поиска всех пар чисел в массиве, сумма которых равна заданному числу. Мы сосредоточимся на двух подходах к проблеме .
При первом подходе мы найдем все такие пары независимо от их уникальности. Во втором мы найдем только уникальные комбинации чисел, удалив лишние пары.
Для каждого подхода мы представим две реализации — традиционную реализацию с использованием циклов for и вторую с использованием Java 8 Stream API.
2. Вернуть все совпадающие пары
Мы будем перебирать массив целых чисел, находя все пары ( i и j ), которые в сумме дают заданное число ( sum ), используя подход грубой силы с вложенным циклом. Этот алгоритм будет иметь сложность времени выполнения O(n 2 ) .
Для наших демонстраций мы будем искать все пары чисел, сумма которых равна 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. Вернуть все уникальные совпадающие пары
Для этого примера нам придется разработать более умный алгоритм, который возвращает только уникальные комбинации чисел, опуская избыточные пары .
Для этого мы добавим каждый элемент в хеш-карту (без сортировки), предварительно проверив, была ли уже показана пара. Если нет, мы получим и пометим его, как показано (установите поле значения как null ).
Соответственно, используя тот же входной массив, что и раньше, и целевую сумму 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(n) .
Теперь решим задачу с помощью 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. Вывод
В этой статье мы объяснили несколько различных способов найти все пары, которые суммируют заданное число в Java. Мы видели два разных решения, каждое из которых использует два основных метода Java.
Как обычно, все примеры кода, показанные в этой статье, можно найти на GitHub — это проект Maven, поэтому его легко скомпилировать и запустить.