Как освоить Two Pointers на LeetCode: разбор метода с примерами

Первая встреча с LeetCode почти всегда выглядит одинаково: открываешь Two Sum, пишешь два вложенных цикла, отправляешь — и ловишь Time Limit Exceeded. Дальше хуже: на средних задачах вроде 3Sum или Container With Most Water всё тоже упирается в квадратичное решение. Выход не в том, чтобы выучить больше частных случаев, а в освоении одного паттерна — двух указателей.

Зачем он вообще нужен

Многие задачи просят найти пару, тройку или подмассив с определённым свойством. Брутфорс перебирает все комбинации и на больших входных данных просто не успевает. Two Pointers использует тот факт, что массив отсортирован (или его можно отсортировать), и за один шаг отбрасывает целый кусок невозможных вариантов.

Работает это как игра «горячо-холодно». Ставишь один указатель в начало, второй — в конец. Сумма слишком маленькая? Единственный способ её увеличить — сдвинуть левый указатель вправо. Слишком большая? Сдвигаешь правый влево. Каждый шаг даёт точную информацию, и ты никогда не возвращаешься к уже отброшенным состояниям.

Базовый приём на примере Two Sum II

Классическая задача: массив уже отсортирован, надо найти два числа, дающих target, и вернуть их индексы (с единицы).

def two_sum(numbers, target):
  left, right = 0, len(numbers)-1
  while left < right:
    current = numbers[left] + numbers[right]
    if current == target:
      return [left+1, right+1]
    elif current < target:
      left += 1
    else:
      right -= 1
  return []

Почему это работает: благодаря сортировке сдвиг левого указателя увеличивает сумму, сдвиг правого — уменьшает. Каждая итерация гарантированно исключает минимум один индекс, поэтому суммарно нужно не больше n шагов. Итог — O(n) времени и O(1) памяти вместо O(n²) и вложенных циклов.

Сравнение: брутфорс против двух указателей

Типичные ошибки

1. Забыть отсортировать массив, если это не гарантировано условием. Сортировка добавляет O(n log n), но это всё равно лучше, чем O(n²).
2. Двигать оба указателя одновременно. Нужно двигать только тот, который ведёт к цели. Иначе легко проскочить правильную пару.
3. Ошибиться в условии цикла: писать left <= right. Когда указатели встретились, все осмысленные пары уже рассмотрены.
4. После сортировки потерять исходные индексы. Если ответ требует индексы, сохраняй пары (значение, индекс) до сортировки.

Куда двигаться дальше

Два указателя — это не одна конкретная задача, а образ мышления. 3Sum сводится к фиксации одного элемента и применению двух указателей к остатку. Container With Most Water — указатели с берегов, двигается сторона с меньшей высотой. Remove Duplicates from Sorted Array — то же самое, но оба указателя идут в одну сторону. А скользящее окно на подмассивах с положительными числами — ближайший родственник этой идеи.

Практический план

Возьми задачу с тегом Two Pointers на LeetCode. Прежде чем писать код, нарисуй массив на бумаге и спроси себя: что станет с суммой, если я подвину left? Что будет, если подвинуть right? Начни с Two Sum II, потом переходи к 3Sum, Container With Most Water и Remove Duplicates.

Когда освоишь движение навстречу друг другу, попробуй fast/slow указатели на связных списках — там та же логика, но с другой скоростью. Этот навык пригодится и на собеседованиях, и при чтении чужого кода: паттерн виден почти сразу, если знаешь, куда смотреть.