Поиск пары элементов массива с заданной суммой

Условие

Дан массив целых чисел numbers и целевое значение requiredSum. Нужно вернуть любые два числа из массива, сумма которых равна requiredSum.

Ввод: numbers = [3, 4, 15, 2, 6], requiredSum = 10 Вывод: [2, 8] или [6, 4] — если такие элементы присутствуют в массиве.

public class Solution {
    public int[] twoSum(int[] nums, int targetSum) {
        // TODO
        return new int[0];
    }
}

Ответ

Храните просмотренные числа в HashSet и для каждого x ищите targetSum − x. В данном примере подходит пара 4 и 6; пары 2 и 8 нет, поскольку 8 отсутствует в массиве.

public int[] twoSum(int[] nums, int targetSum) {
    var seen = new java.util.HashSet<Integer>();
    for (int x : nums) {
        long need = (long) targetSum - x;
        if (need >= Integer.MIN_VALUE && need <= Integer.MAX_VALUE
                && seen.contains((int) need))
            return new int[]{(int) need, x};
        seen.add(x);
    }
    return new int[0];
}

Поиск выполняется до добавления текущего числа, поэтому один элемент не используется дважды; одинаковые значения допустимы при двух вхождениях. Время в среднем O(n), память O(n). long защищает вычисление дополнения от переполнения.