Два указателя (two pointers)

Один из самых частых приёмов: два индекса вместо вложенного цикла.

Два указателя — приём, где два индекса движутся навстречу друг другу или в одном направлении, сводя задачу с O(n^2) к O(n).

Идея приёма

Вместо перебора всех пар (O(n^2)) мы ставим один указатель в начало, другой в конец отсортированного массива и сдвигаем тот, который «виноват» в неправильной сумме. Так каждый элемент посещается максимум один раз.

Классическая задача: Two Sum II

Дан отсортированный массив и число target. Нужно найти два элемента, дающих в сумме target, и вернуть их индексы. Если сумма больше нужной — двигаем правый указатель влево (уменьшаем сумму). Если меньше — двигаем левый вправо.

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

print(two_sum_sorted([2, 7, 11, 15], 9))
print(two_sum_sorted([1, 3, 4, 5, 8], 12))
print(two_sum_sorted([1, 2, 3], 100))

Вывод:

[0, 1]
[2, 4]
[-1, -1]

Другой паттерн: указатели в одном направлении

Удаление дубликатов из отсортированного массива на месте: медленный указатель отмечает позицию для записи, быстрый сканирует.

def remove_duplicates(arr):
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

nums = [1, 1, 2, 2, 2, 3, 4, 4]
k = remove_duplicates(nums)
print(k, nums[:k])

Вывод:

4 [1, 2, 3, 4]

Как работает под капотом

Корректность для Two Sum II опирается на отсортированность. Если текущая сумма больше target, то любой элемент правее right в паре с left даст ещё больше — значит right можно безопасно сдвинуть влево, не потеряв решение. Симметрично для left. Каждый шаг сдвигает ровно один указатель, и они встречаются за n шагов — отсюда O(n) время и O(1) память.

Частые ошибки

Применять приём к неотсортированному массиву — тогда логика сдвига ломается (для несортированного Two Sum нужен хеш).
Условие while left <= right вместо while left < right: элемент нельзя складывать сам с собой.
Забыть случай «решения нет» и не вернуть запасное значение.

Итог

Два указателя превращают O(n^2) в O(n) на отсортированных данных.
Навстречу — для пар и сумм; в одном направлении — для фильтрации на месте.
Память O(1): ничего, кроме пары индексов, не создаём.