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

Два указателя — это приём, при котором массив обрабатывают с помощью двух индексов. Указатели могут двигаться навстречу друг другу, например от начала и конца массива, или последовательно, поддерживая границы обрабатываемой части.

Перед применением приёма важно понимать, что такое индекс массива и как выполняется обычный перебор элементов массива. Метод особенно полезен, когда условие задачи позволяет после проверки элемента навсегда исключить его из дальнейшего рассмотрения. Тогда каждый указатель проходит свою часть последовательности не более одного раза.

Как работает приём

При движении навстречу указатели часто называют \(l\) и \(r\): \(l\) начинается слева, а \(r\) — справа. Пока \(l \le r\), проверяют элементы \(a_l\) и \(a_r\), затем сдвигают один или оба индекса. Например, так можно искать пару элементов с заданной суммой в отсортированном массиве: если сумма слишком мала, увеличивают \(l\), а если слишком велика — уменьшают \(r\).

a = [1, 2, 3, 4, 5]
l, r = 0, len(a) - 1
while l < r:
    a[l], a[r] = a[r], a[l]
    l += 1
    r -= 1