Два указателя

Условие

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

Идея

Ставим левый указатель на начало, правый — на конец. Если сумма меньше x, двигаем левый вправо: правый уменьшать бессмысленно, сумма только упадёт. Если больше — двигаем правый влево. Каждый шаг отбрасывает один элемент, поэтому шагов не больше n.

def pair_with_sum(a, x):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == x:
            return i, j
        if s < x:
            i += 1
        else:
            j -= 1
    return None

Время O(n), память O(1).