Два указателя

Идея двух указателей

Многие задачи на массивах «в лоб» решаются вложенными циклами — перебором всех пар, это O(n²). МетодФункция, привязанная к объекту и вызываемая через точку: text.upper(). двух указателей часто убирает один циклКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно.: мы заводим два индексаНомер позиции элемента в последовательности. В Python нумерация с нуля: первый элемент — индекс 0. и двигаем их навстречу друг другу или в одном направлении, опираясь на свойства данных. Получается один проход — O(n).

Классический случай — отсортированный массив, в котором нужно найти пару с заданной суммой. Ставим один указатель в начало (left), другой в конец (right) и смотрим на сумму краёв.

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

Второй сценарий: указатели в одном направлении

Два указателя бывают и «догоняющими»: медленный и быстрый идут слева направо. Так удаляют дубликаты или сдвигают элементы. Например, перенос всех нулей в конец спискаИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list.: slow отмечает место для следующего ненулевого, fast сканирует массив.

Вернётся True и False. Указатели идут навстречу и сравнивают симметричные символы; при первом несовпадении — не палиндром. Это O(n) и без создания перевёрнутой копии строки.

⚠️ Частые ошибки новичков

Ошибка. Применить два указателя «навстречу» к неотсортированному массиву для поиска суммы. Логика сдвига опирается на упорядоченность; на хаотичных данных она пропустит ответ. Если массив не отсортирован — сначала сортируйте или используйте хеш-множествоКоллекция уникальных элементов без порядка: {1, 2, 3}. По-английски set. (следующий урок). Запустите код: для [8, 1, 11, 3] пара на 12 существует (1+11), но метод её не найдёт.