Первая встреча с 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²) и вложенных циклов.
Сравнение: брутфорс против двух указателей
| Брутфорс | Два указателя | |
|---|---|---|
| Время | O(n²) | O(n) |
| Память | O(1), но иногда O(n) для hash map | O(1) |
| Код | Проще, но падает на больших n | Чуть сложнее, зато летает |
| Требование | Любой массив | Отсортированный или сортируемый |
Типичные ошибки
- Забыть отсортировать массив, если это не гарантировано условием. Сортировка добавляет O(n log n), но это всё равно лучше, чем O(n²).
- Двигать оба указателя одновременно. Нужно двигать только тот, который ведёт к цели. Иначе легко проскочить правильную пару.
- Ошибиться в условии цикла: писать left <= right. Когда указатели встретились, все осмысленные пары уже рассмотрены.
- После сортировки потерять исходные индексы. Если ответ требует индексы, сохраняй пары (значение, индекс) до сортировки.
Куда двигаться дальше
Два указателя — это не одна конкретная задача, а образ мышления. 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 указатели на связных списках — там та же логика, но с другой скоростью. Этот навык пригодится и на собеседованиях, и при чтении чужого кода: паттерн виден почти сразу, если знаешь, куда смотреть.
Fluxs
Комментарии (0)
Войдите, чтобы комментировать.
Пока нет комментариев. Будьте первым.