4. Найти два числа в неотсортированном массиве с заданной суммой
Условие задачи:
Дан неотсортированный массив целых чисел nums и целевое значение target.
Необходимо найти два разных элемента массива, сумма которых равна target, и вернуть найденную пару.
Если подходящей пары нет, вернуть пустой массив.
Пример 1:
nums = [2, 7, 11, 15]
target = 9
Результат: [2, 7]
Пример 2:
nums = [3, 2, 4]
target = 6
Результат: [2, 4]
Спойлеры к решению
Подсказки
💡 Поскольку массив не отсортирован, подход с двумя указателями напрямую не подходит.
💡 Для каждого числа вычисли, какое значение нужно ему в пару:
💡 Уже просмотренные элементы удобно хранить в
💡 Если нужное значение уже встречалось, пара найдена.
💡 Для каждого числа вычисли, какое значение нужно ему в пару:
target - num.💡 Уже просмотренные элементы удобно хранить в
HashSet.💡 Если нужное значение уже встречалось, пара найдена.
Решение
public static int[] findTwoSum(int[] nums, int target) {
Set<Long> seen = new HashSet<>();
for (int num : nums) {
long complement = (long) target - num;
if (seen.contains(complement)) {
return new int[]{(int) complement, num};
}
seen.add((long) num);
}
return new int[0];
}
Для каждого элемента вычисляется недостающее число:
long complement = (long) target - num;
Например, если:
target = 9
num = 7
то нужно найти:
9 - 7 = 2
Если 2 уже есть среди просмотренных элементов:
if (seen.contains(complement))
значит подходящая пара найдена.
Для массива:
[2, 7, 11, 15]
при обработке 7 множество уже содержит 2, поэтому результат:
[2, 7]
Используется long при вычислении разницы, чтобы избежать переполнения int на граничных значениях.
Временная сложность в среднем — O(n), дополнительная память — O(n).
Менее эффективный вариант — проверить все пары двумя вложенными циклами за O(n²).