Алгоритмы
Two Pointers: Встречное движение
Цели урока
- Понимать два паттерна: встречное и параллельное движение
- Решать Two Sum в отсортированном массиве за O(n)
- Удалять дубликаты in-place
- Определять цикл в списке (Floyd's algorithm)
- Применять three pointers для 3Sum
Предварительные знания
- Массивы
- Бинарный поиск
Каждое второе собеседование в FAANG включает задачу на two pointers. Это не просто техника - это образ мышления: как превратить O(n²) в O(n).
- Слияние отсортированных массивов (merge sort)
- Поиск конфликтов в расписаниях
- Streaming алгоритмы, обработка данных с ограниченной памятью
- Обнаружение циклов в графах и списках
Фольклорный приём эпохи спортивного программирования
У техники двух указателей нет единственного автора и нет основополагающей статьи. Это фольклорный приём, та идея, которую переоткрывают многие, потому что она естественно вытекает из распространённых задач. Шаг слияния в merge sort, описанный Джоном фон Нейманом в 1945 году, уже идёт двумя индексами по двум отсортированным массивам. Шаг разбиения в quicksort Тони Хоара в 1961 году ведёт указатель с каждого конца. Превратили этот шаблон в названный и преподаваемый приём спортивное программирование и подготовка к собеседованиям начиная с 1990-х, когда тренеры заметили, что целое семейство задач на массивы и строки сводится с O(n в квадрате) к O(n), если поддерживать два индекса с ясным инвариантом. Сайты вроде Codeforces, TopCoder, а позже LeetCode сделали два указателя стандартным пунктом в наборе приёмов решения задач.
Идея: два указателя
**Two Pointers** - техника использования двух индексов для обхода массива. Вместо вложенных циклов O(n²) - один проход O(n).
**Когда применять:** отсортированный массив, поиск пар, палиндромы, удаление дубликатов, слияние массивов.
Какая сложность у наивного поиска пары с заданной суммой (два вложенных цикла)?
Встречное движение
**Классическая задача: Two Sum в отсортированном массиве**
**Почему это работает?**
**Массив ДОЛЖЕН быть отсортирован!** Для неотсортированного - используй хеш-таблицу (классический Two Sum).
arr = [1, 3, 5, 7, 9], target = 12. После первого шага (1 + 9 = 10 < 12):
Параллельное движение
**Оба указателя двигаются в одном направлении.** Классика - удаление дубликатов in-place.
**Fast & Slow pointer - для связных списков:**
**Идея:** если есть цикл, быстрый указатель "догонит" медленного. Как бегуны на круговой дорожке.
Зачем нужен slow pointer при удалении дубликатов?
Классические задачи
**1. Проверка палиндрома:**
**2. Container With Most Water:**
**3. Trapping Rain Water** (сложнее):
В Container With Most Water, почему двигаем указатель с меньшей высотой?
Расширение: три указателя
**3Sum - найти все тройки с суммой 0:**
**Dutch National Flag (3-way partition):**
**Паттерн:** фиксируем один элемент, применяем two pointers к остальным. 3Sum → 4Sum → kSum.
Сложность 3Sum с использованием two pointers (после сортировки)?
Two Pointers
- Встречное: left и right сходятся к центру
- Параллельное: slow и fast в одном направлении
- Требует отсортированных данных или особой структуры
- Превращает O(n²) в O(n)
- Расширяется до 3+ указателей
Связанные темы
Two Pointers часто комбинируется с другими техниками.
- Sliding Window — Особый случай параллельного движения
- Binary Search — Альтернатива для поиска
- Merge Sort — Использует two pointers при слиянии
Связанные уроки
- alg-10-binary-search — Сходимость указателей опирается на логику отсортированного массива
- alg-27-sliding-window — Однонаправленные указатели обобщаются до скользящего окна
- alg-05-merge-sort — Слияние двух массивов двигает два указателя согласованно
- ds-02-linked-lists — Быстрый/медленный указатели находят циклы в списках
- ds-01-arrays