Нахождение двух элементов массива с требуемой суммой

Условие

Дан массив целых чисел, нумерация начинается с 1, упорядоченный по возрастанию (неубывающий). Требуется определить пару чисел, сумма которых равна заданному значению target. Обозначим эти элементы как arr[i] и arr[j], где 1 ≤ i < j ≤ arr.length. Необходимо вернуть их позиции в виде массива из двух элементов [i, j].

Пример 1: Ввод: arr = [2, 7, 11, 15], target = 9 Вывод: [1, 2] Пояснение: 2 + 7 = 9, следовательно i = 1, j = 2.

Пример 2: Ввод: arr = [-1, 0], target = -1 Вывод: [1, 2] Пояснение: -1 + 0 = -1, значит i = 1, j = 2.

Ответ

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

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1
    return None

Неубывающая сортировка делает каждый сдвиг обоснованным. Один элемент не используется дважды, потому что left < right. Время O(n), память O(1). При нескольких допустимых парах возвращается первая найденная.