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

Метод двух указателей использует два индекса, которые движутся по структуре навстречу или в одну сторону. Это превращает потенциально квадратный перебор в линейный. Часто применяется на отсортированных массивах.

Сложность: время O(n); память: O(1). Классические задачи: поиск пары с заданной суммой, проверка палиндрома, слияние двух массивов.

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

print(two_sum_sorted([1, 3, 4, 7, 9], 11))  # (1, 3)