Найти 2 элемента упорядоченного массива, сумма которых равна заданному числу

3. Найти два числа в отсортированном массиве с заданной суммой

Условие задачи:
Дан отсортированный по возрастанию массив целых чисел nums и целевое значение target.

Необходимо найти два разных элемента массива, сумма которых равна target, и вернуть найденную пару.

Если подходящей пары нет, вернуть пустой массив.

Пример 1:

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 10

Результат: [1, 9]

Пример 2:

nums = [2, 3, 4]
target = 6

Результат: [2, 4]

Спойлеры к решению

Подсказки

💡 Поскольку массив отсортирован, удобно использовать два указателя.
💡 Левый указатель поставь в начало массива, правый — в конец.
💡 Если сумма меньше target, нужно увеличить левый указатель.
💡 Если сумма больше target, нужно уменьшить правый указатель.
💡 Когда сумма совпала с target, пара найдена.

Решение

public static int[] findTwoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        long sum = (long) nums[left] + nums[right];

        if (sum == target) {
            return new int[]{nums[left], nums[right]};
        }

        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[0];
}

Идея алгоритма:

left                          right
 ↓                              ↓
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Если:

sum < target

то левый элемент слишком маленький, поэтому двигаем left вправо.

Если:

sum > target

то правый элемент слишком большой, поэтому двигаем right влево.

Для массива:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

и target = 10 первая проверка сразу даст:

1 + 9 = 10

поэтому результат:

[1, 9]

Сумма вычисляется через long, чтобы избежать переполнения int при сложении больших значений.

Временная сложность — O(n), дополнительная память — O(1).