«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, поэтому его легко скомпилировать и запустить.
«