Паттерны FAANG: Два указателя и Скользящее окно

Классификация паттерна двух указателей: Сходящиеся, параллельные и быстрые/медленные указатели

Самый интуитивный способ найти пару элементов в массиве, удовлетворяющую заданному условию — перебрать все возможные комбинации. Для каждого элемента мы запускаем внутренний цикл, который сканирует оставшуюся часть массива. При размере входных данных (типичное ограничение в задачах FAANG-интервью) такой подход генерирует порядка операций. Как мы знаем из оценки алгоритмической сложности, квадратичное время на таких объемах неминуемо приводит к превышению лимита времени (Time Limit Exceeded). Оптимизация подобных задач требует отказа от вложенных итераций в пользу однопроходных алгоритмов. Главным инструментом для этого служит паттерн «Два указателя» (Two Pointers).

В контексте языка Python и работы с массивами (списками), термин «указатель» не означает физический адрес в оперативной памяти, как в языках C или C++. Здесь указатель — это целочисленная переменная, хранящая индекс элемента. Суть паттерна заключается в одновременном управлении двумя такими индексами, которые перемещаются по структуре данных по определенным правилам. Это позволяет анализировать отношения между двумя элементами за один проход, снижая временную сложность до линейной .

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

Сходящиеся указатели (Converging Pointers)

Эта стратегия применяется, когда необходимо проанализировать пары элементов, находящиеся на противоположных концах структуры данных, и постепенно сужать диапазон поиска к центру.

Базовая конфигурация:

Левый указатель (left) инициализируется индексом .

Правый указатель (right) инициализируется индексом , где — длина массива.

Цикл продолжается до тех пор, пока выполняется условие .

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

Если массив отсортирован по возрастанию, сумма элементов на краях дает нам базовую точку отсчета: , где — массив, а и — текущие индексы. Далее вступает в силу строгая математическая логика:

Если , пара найдена.

Если , нам нужно увеличить итоговую сумму. Поскольку массив отсортирован, сдвиг правого указателя влево только уменьшит сумму (или оставит неизменной). Единственный способ получить большее значение — сдвинуть левый указатель вправо ().

Если , сумму нужно уменьшить. Сдвиг левого указателя вправо сделает ее еще больше. Значит, необходимо сдвинуть правый указатель влево ().

Математика отсечения пространства поиска

На первый взгляд может показаться, что сдвигая указатели навстречу друг другу, мы рискуем пропустить правильную пару. Почему алгоритм гарантированно находит ответ, если он существует?

Представим все возможные пары индексов как двумерную матрицу размером . Наша задача — найти ячейку в этой матрице. Брутфорс проверяет каждую ячейку.

!Матрица пространства поиска и процесс отсечения строк и столбцов

Когда мы стоим на позициях и , и обнаруживаем, что , мы делаем шаг . Этим единственным действием мы не просто переходим к следующему элементу. Мы математически доказываем, что текущий элемент в паре с любым элементом левее даст сумму еще меньше, чем текущая (которая уже меньше ). Следовательно, вся строка в матрице возможных пар, соответствующая текущему , может быть безопасно отброшена. За одну операцию проверки мы отсекаем ложных вариантов.

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

Нюансы граничных условий

Критически важным аспектом является условие цикла: против . В задачах на поиск уникальных пар (как описано выше) используется строгое неравенство . Если допустить равенство, указатели сойдутся на одном и том же элементе, и алгоритм может ошибочно вернуть , использовав один элемент дважды, что обычно запрещено условиями.

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

Параллельные указатели (Parallel Pointers)

Вторая категория паттерна применяется при работе с двумя независимыми структурами данных (или двумя независимыми сегментами одной структуры). Указатели движутся в одном направлении, но каждый привязан к своему массиву.

Базовая конфигурация:

Указатель инициализируется нулем для массива .

Указатель инициализируется нулем для массива .

Движение указателей зависит от сравнения элементов и .

Самый известный сценарий использования параллельных указателей — слияние двух отсортированных массивов в один (фаза Merge в алгоритме Merge Sort).

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

Проблема «хвостов» (Exhaustion)

Сложность параллельных указателей кроется в рассинхронизации длины массивов или скорости движения указателей. Основной цикл while i < len(A) and j < len(B) неизбежно завершится, как только один из массивов будет полностью пройден.

В этот момент во втором массиве может остаться «хвост» — последовательность элементов, которые гарантированно больше всех уже добавленных в результат (поскольку массивы изначально отсортированы). Ошибка новичков — забыть обработать этот остаток. Два дополнительных цикла while в коде выше решают эту проблему. Поскольку к моменту их вызова один из указателей уже вышел за границы, выполнится только один из этих циклов.

Временная сложность такого подхода составляет , где и — длины массивов и соответственно. Как мы разбирали в правилах математики Big O, мы используем независимые переменные, так как размеры структур не связаны друг с другом. Пространственная сложность в данном случае также из-за необходимости выделения памяти под новый массив merged.

Быстрые и медленные указатели (Fast and Slow Pointers)

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

Эта стратегия является фундаментом для In-place алгоритмов, где требуется модифицировать массив без выделения дополнительной памяти, сохраняя пространственную сложность .

В этом паттерне указатели приобретают четкие семантические роли:

Быстрый указатель (Fast Reader) — выступает в роли разведчика. Он сканирует массив элемент за элементом, проверяя их на соответствие условию задачи.

Медленный указатель (Slow Writer) — выступает в роли хранителя состояния. Он указывает на позицию, куда должен быть записан следующий валидный элемент, найденный «разведчиком».

Рассмотрим задачу удаления дубликатов из отсортированного массива. Требуется оставить только уникальные элементы в начале массива и вернуть их количество. Дополнительную память использовать нельзя.

Если массив отсортирован, все дубликаты располагаются блоками (например, [1, 1, 2, 2, 2, 3]). Быстрый указатель будет бежать вперед, пропуская повторяющиеся значения. Как только он встретит новое, ранее не виданное число, он должен скопировать его на позицию, которую охраняет медленный указатель, после чего медленный указатель сдвинется на один шаг.

!Пошаговая перезапись массива быстрым и медленным указателями

Механика In-place перезаписи

В этом алгоритме мы эксплуатируем тот факт, что медленный указатель никогда не может обогнать быстрый. В худшем случае (когда дубликатов нет вообще, например [1, 2, 3]), slow и fast будут двигаться синхронно, и алгоритм будет перезаписывать элементы самими собой ().

Как только fast натыкается на дубликат, он уходит вперед, оставляя slow позади. Образуется разрыв. Этот разрыв — это «мусорная» зона массива, содержащая дубликаты. Когда fast находит новое уникальное число, операция arr[slow] = arr[fast] безопасно затирает один из старых дубликатов полезными данными.

Мы не удаляем элементы физически (в статических массивах под капотом Python list удаление из середины потребовало бы сдвига всех последующих элементов, что дало бы сложность ). Вместо этого мы переносим нужные данные в начало. Временная сложность остается строго , так как быстрый указатель проходит по каждому элементу ровно один раз. Память — , так как мы используем только две целочисленные переменные.

Стратегии выбора паттерна

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

Маркеры сходящихся указателей:

- Входной массив отсортирован (или его можно отсортировать за без нарушения логики задачи). - Требуется найти пару элементов (сумма, разность, произведение). - Задача связана с симметрией (палиндромы, инверсия массива с двух концов).

Маркеры параллельных указателей:

- На вход подаются два (или более) массива или списка. - Требуется объединить данные, найти пересечение элементов или сравнить последовательности.

Маркеры быстрых и медленных указателей:

- Требуется модифицировать массив In-place (без выделения памяти). - Нужно удалить элементы по определенному условию, сгруппировать нули в конце массива или отфильтровать данные. - (Забегая вперед) Требуется найти цикл или середину в связном списке.

Паттерн двух указателей меняет парадигму мышления. Вместо того чтобы заставлять один элемент проверять все остальные (вложенные циклы), мы выстраиваем хореографию двух независимых агентов (индексов), которые совместно исследуют структуру данных, опираясь на ее свойства — будь то отсортированность или физическая непрерывность памяти. Это базовый, но невероятно мощный инструмент, который станет фундаментом для изучения скользящего окна в следующих главах.