КабинетПоиск
Алгоритмы и структуры данных

Two Pointers and Sliding Window

Два указателя: семейство приёмов

актуальноТекущий рабочий стандарт

Направления: Основы · Алгоритмы и структуры данных

Зонтичная тема: что общего у четырёх приёмов с двумя индексами и как выбрать нужный. Сами приёмы разобраны каждый на своей странице.

Ключевые тезисы

  • Общее у всех вариантов одно: два индекса, каждый идёт только вперёд, суммарно — один проход по входу.
  • Граница применимости тоже общая: сдвиг указателя должен быть необратимым решением.
  • Выбор варианта определяют три вопроса: подряд ли элементы, отсортирован ли вход, один ли это источник данных.

Какую задачу решает

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

Эта страница — про семейство целиком: что у вариантов общее, по каким вопросам выбирается нужный и на чём спотыкаются во всех четырёх. Сами приёмы разобраны каждый на своей странице, по одной и той же схеме из десяти шагов.

Внутри темы

4 приёма разобраны на отдельных страницах — по одной и той же схеме. Эта страница про то, что у них общее и как выбрать нужный.

Opposite-Direction Pointersактуально

Встречные указатели

Два индекса сходятся с концов отсортированного массива. На каждом шаге отбрасывается конец, который заведомо не даст лучшего ответа, — и вместе с ним целая полоса пар.

Sliding Windowактуально

Скользящее окно

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

Fast and Slow Pointersактуально

Быстрый и медленный указатель

Два указателя идут в одну сторону с разной скоростью. Если структура зациклена, быстрый догоняет медленного — цикл находится без журнала посещённых узлов.

Same-Direction Pointersактуально

Два указателя в одну сторону

Слияние, пересечение и запись на месте: каждому источнику свой указатель, ни один не откатывается назад. Основа сортировки слиянием и merge join в базах данных.

Подробный разбор

3 подтемы — объяснения, формулы, примеры и интерактивные графики.

Четыре приёма семейства выглядят по-разному, но держатся на одном и том же. В задаче есть два индекса; каждый из них движется только вперёд по своему правилу; за весь алгоритм каждый проходит массив не больше одного раза. Отсюда линейное время: не потому, что цикл один, а потому, что суммарное число сдвигов ограничено длиной входа.

ВариантКуда движутся указателиЧто даёт
Встречные указателис двух концов навстречупары и тройки в отсортированном массиве
Скользящее окнооба слева направо, между нимиподотрезки с ограничением
Быстрый и медленныйв одну сторону с разной скоростьюцикл, середина, k-й с конца
В одну сторонупо своему источнику каждыйслияние, пересечение, запись на месте
На практике

Общая же граница применимости тоже одна: сдвиг указателя должен быть необратимым решением. Если может выясниться, что границу надо вернуть назад, приём неприменим — и дальше идут префиксные суммы, или динамика.

  1. Элементы должны идти подряд? Да — скользящее окно. Нет — дальше.
  2. Вход отсортирован и ищется пара или тройка? Да — встречные указатели. Нет — дальше.
  3. Данных два набора или нужна запись на месте? Да — указатели в одну сторону.
  4. Структура — список или последовательность состояний, вопрос про цикл, середину или k-й с конца? Быстрый и медленный.

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

На практике

Разбор сигналов по всей главе собран отдельно — в теме как распознать паттерн задачи.

  • Длина окна или отрезка. Между индексами left и right включительно лежит right - left + 1 элементов, а не right - left. Это самая частая ошибка на единицу во всём семействе.
  • Состояние не обновлено при сдвиге. Указатель сдвинулся, а счётчик, сумма или множество остались прежними — решение начинает врать на второй половине входа.
  • Указатель пошёл назад. Как только в коде появляется откат границы, линейность теряется, а вместе с ней и весь смысл приёма: скрытый квадрат выглядит как один цикл.
На практике

Проверять это дешевле всего на трёх входах: пустом, из одного элемента и из одинаковых элементов. Они ловят почти все ошибки границ, и разобрать их руками быстрее, чем отлаживать по падающему тесту.

Чем заменяют

Prefix SumsактуальноПрефиксные суммы · Алгоритмы и структуры данныхРечь про суммы, а значения могут быть отрицательными.Hash TablesактуальноХеш-таблицы · Алгоритмы и структуры данныхПорядка во входе нет, а искать нужно по значению.Dynamic ProgrammingактуальноДинамическое программирование · Алгоритмы и структуры данныхЭлементы ответа не обязаны идти подряд.

Видеолекции

Тайм-кода именно на эту тему в записях нет. Но глава «Алгоритмы и структуры данных» разобрана в курсе целиком — с той оговоркой, что место в записи придётся искать самому.

Курс: Алгоритмы и структуры данных17 записей

Связанные темы

Два указателя и окно

Opposite-Direction Pointers90%

Встречные указатели · Алгоритмы и структуры данных

Два индекса сходятся с концов отсортированного массива. На каждом шаге отбрасывается конец, который заведомо не даст лучшего ответа, — и вместе с ним целая полоса пар.

Sliding Window90%

Скользящее окно · Алгоритмы и структуры данных

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

Fast and Slow Pointers90%

Быстрый и медленный указатель · Алгоритмы и структуры данных

Два указателя идут в одну сторону с разной скоростью. Если структура зациклена, быстрый догоняет медленного — цикл находится без журнала посещённых узлов.

Same-Direction Pointers90%

Два указателя в одну сторону · Алгоритмы и структуры данных

Слияние, пересечение и запись на месте: каждому источнику свой указатель, ни один не откатывается назад. Основа сортировки слиянием и merge join в базах данных.

Prefix Sums90%

Префиксные суммы · Алгоритмы и структуры данных

Один предварительный проход превращает сумму на любом отрезке в одно вычитание. Тот же приём вместе с хеш-таблицей находит подотрезок с заданной суммой за линейное время.

Monotonic Stack and Deque90%

Монотонный стек и дек · Алгоритмы и структуры данных

Приём поверх стека: хранить только тех, для кого ответ ещё не найден. Даёт ближайший больший элемент для всех позиций сразу и максимум в скользящем окне — за один проход.

Следующий шагДальше по связи: Opposite-Direction PointersДва индекса сходятся с концов отсортированного массива. На каждом шаге отбрасывается конец, который заведомо не даст лучшего ответа, — и вместе с ним целая полоса пар.Перейти →
← String AlgorithmsOpposite-Direction Pointers →

Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.