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

Интуиция: два человека у книжной полки

Представь длинную полку с книгами, расставленными по толщине: слева самые тонкие, справа самые толстые. Нужно найти две книги, которые вместе дают ровно 10 см. Можно перебрать все пары, но это долго. Лучше встать вдвоём у краёв полки: один берёт самую тонкую книгу, другой самую толстую.

• Если вместе слишком толсто, правый меняет свою книгу на соседнюю, потоньше.
• Если слишком тонко, левый берёт книгу потолще.
• Если ровно, пара найдена.

Вы идёте навстречу друг другу и ни разу не возвращаетесь назад. На этом и держится приём двух указателей: вместо вложенного перебора O(n²) ты ведёшь по массиву два индекса и за один проход получаешь O(n).

Два вида двух указателей

Вид	Как двигаются	Где встречается
С двух концов	left с начала, right с конца, навстречу друг другу	пара с суммой в отсортированном массиве, проверка палиндрома, разворот массива
В одну сторону (быстрый и медленный)	оба идут слева направо, fast впереди, slow отстаёт	фильтрация на месте, удаление дубликатов, поиск цикла в списке

Палиндром проверяется самым естественным образом: сравниваешь s[left] и s[right], и если символы совпали, сдвигаешь оба указателя к центру. Первое несовпадение означает, что строка не палиндром. Если указатели встретились без несовпадений, это палиндром.

Быстрый и медленный удобно представлять как чтение и запись. fast читает каждый элемент, а slow указывает, куда записать следующий «хороший». Например, если надо оставить в массиве только чётные числа, fast пробегает всё подряд, а каждый чётный элемент копируется в позицию slow, после чего slow сдвигается на один.

Пошагово: пара с суммой 10

Возьмём отсортированный массив и target = 10.

(На шаге 4 было 3 + 6 = 9 < 10, поэтому left сдвинулся на 4.)

Почему можно смело выкидывать элемент

Это ключевой момент, его стоит понять, а не заучить.

• Если nums[left] + nums[right] > target, то правый элемент даже в паре с самым маленьким из оставшихся даёт перебор. С любым другим будет ещё больше, так что nums[right] ни в какую подходящую пару не входит и его можно отбросить.
• Симметрично, если сумма меньше target, то nums[left] даже с самым большим из оставшихся даёт недобор, поэтому он тоже бесполезен.

Каждый шаг отсекает один заведомо ненужный элемент, и правильный ответ при этом не теряется.

Шаблон кода

def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:                 # указатели ещё не встретились
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]        # нашли пару
        if s < target:
            left += 1                   # мало — берём число побольше
        else:
            right -= 1                  # много — берём число поменьше
    return []                           # пары нет

Сложность: почему O(n)

• Время O(n). Вначале между указателями n − 1 позиций. На каждой итерации ровно один указатель делает шаг внутрь, и расстояние уменьшается на 1. Значит, итераций не больше n − 1. Указатели никогда не откатываются назад, поэтому каждый элемент просматривается не более одного раза.
• Память O(1). Нужны только два индекса и сумма.

Для сравнения: перебор всех пар стоит O(n²), а хеш-таблица даёт O(n) по времени, но требует O(n) памяти. На отсортированном массиве два указателя выигрывают у обоих вариантов.

Когда на собесе думать о двух указателях

Сигналы в условии:

• массив отсортирован (или его можно отсортировать за O(n log n)), и ищется пара или тройка с заданной суммой;
• требуется сделать что-то на месте, «без дополнительной памяти»: удалить, сдвинуть, отфильтровать;
• проверка симметрии: палиндром, разворот;
• в связном списке нужно найти середину или цикл. Здесь работает вариант быстрого и медленного указателей.

Как проговорить вслух: «Массив отсортирован, поэтому поставлю указатели на оба конца. Если сумма больше цели, правый элемент точно не войдёт в ответ, и я сдвигаю right. Если меньше, сдвигаю left. Каждый шаг отбрасывает один элемент, поэтому получается O(n) по времени и O(1) по памяти». Объяснение, почему можно отбросить элемент, интервьюер ценит больше, чем сам код.

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

• left <= right вместо left < right. Тогда элемент может сложиться сам с собой. Для пары разных элементов условие строгое.
• Применять приём к неотсортированному массиву. Без сортировки логика «больше или меньше» перестаёт работать. Сначала отсортируй или возьми хеш-таблицу.
• Сортировать, когда нужны исходные индексы. После сортировки индексы меняются, поэтому храни пары (значение, исходный индекс).
• Сдвигать оба указателя сразу без причины. На каждом шаге двигается тот указатель, чей элемент гарантированно бесполезен.
• Переполнение суммы в Java, C++ и Go при больших числах. Если значения близки к пределу int, считай сумму в long.

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