Для нахождения всех пар элементов в массиве, сумма которых равна заданному числу, можно использовать два подхода: перебор всех пар элементов или использование хэш-таблицы. Рассмотрим оба подхода.
- Перебор всех пар элементов:
int[] arr = {2, 4, 6, 8, 10};
int sum = 14;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == sum) {
System.out.println(arr[i] + ", " + arr[j]);
}
}
}
В данном примере мы используем два вложенных цикла for, чтобы перебрать все возможные пары элементов массива и проверить, равна ли их сумма заданному числу. Если это так, то выводим данную пару элементов.
Такой способ имеет временную сложность O(n^2), что не является оптимальным для больших массивов.
- Использование хэш-таблицы:
int[] arr = {2, 4, 6, 8, 10};
int sum = 14;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = sum - arr[i];
if (map.containsKey(complement)) {
System.out.println(arr[i] + ", " + complement);
}
map.put(arr[i], i);
}
В данном примере мы используем хэш-таблицу HashMap, чтобы хранить все элементы массива и их индексы. Затем мы перебираем каждый элемент массива и находим, равен ли его комплемент (разность между суммой и текущим элементом) какому-либо элементу из хэш-таблицы. Если такой элемент есть, то выводим пару элементов.
Такой способ имеет временную сложность O(n), что делает его более эффективным для больших массивов.
Выбор подходящего способа зависит от конкретной задачи. Если массив невелик, то можно использовать первый способ. Но если массив большой, то рекомендуется использовать второй способ с использованием хэш-таблицы.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov