Два указателя в отсортированном массиве
Сдвигайте концы навстречу друг другу, чтобы найти цель
«Два указателя в отсортированном массиве» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Зачем нужны два указателя
Техника двух указателей просматривает массив с помощью двух индексов вместо вложенных циклов, превращая многие идеи с O(n^2) в один аккуратный проход O(n). 🎯
Отсортированный — ключевое слово
Классический вариант требует отсортированного массива. Порядок помогает рассуждать: движение вправо увеличивает значение, а движение влево уменьшает его, поэтому каждый шаг становится осознанным решением.
Два указателя на концах
Установите один указатель на левом конце, а другой — на правом. Они направлены навстречу друг другу и постепенно сокращают расстояние между собой.
left = 0
right = len(a) - 1Сдвиг концов к центру
На каждом шаге сдвигайте ровно один указатель внутрь. Порядок элементов в массиве подсказывает, какую сторону нужно приблизить к цели.
Условие цикла
Продолжайте цикл, пока выполняется условие left < right. Когда указатели встретятся или пересекутся, все полезные пары уже проверены, и можно остановиться.
while left < right:
# inspect a[left] and a[right]
passЧтение текущей суммы
Рассматривайте a[left] + a[right] как текущий кандидат. Сравнение с целевым значением подскажет, нужно ли в следующий раз получить большее или меньшее значение.
total = a[left] + a[right]Слишком мало: сдвигайте левый
Если сумма меньше целевого значения, нужно больше. Сдвиньте левый указатель вправо, к большим значениям, поскольку массив отсортирован по возрастанию.
if total < target:
left += 1Слишком много: сдвигайте правый
Если сумма больше целевого значения, нужно меньше. Сдвиньте правый указатель влево, к меньшим значениям, чтобы уменьшить общую сумму.
elif total > target:
right -= 1Каждый шаг отбрасывает лишнюю работу
Каждый сдвиг отбрасывает целую группу пар, которые уже не нужно проверять. Поэтому проход имеет линейную, а не квадратичную сложность.
Почему алгоритм остаётся правильным
Вы отбрасываете только пары, которые не могут подойти, поэтому правильный ответ никогда не пропускается. Именно эта надёжность делает метод двух указателей заслуживающим доверия на соревнованиях.
За пределами концов
Та же идея лежит в основе разных вариантов: разворота на месте, разбиения и слияния. Освоив указатели, движущиеся навстречу друг другу, Вы легко узнаете этот приём в других задачах.
Быстрая проверка
Вы просматриваете отсортированный массив с обоих концов в поисках заданной суммы.
Повторение
Два указателя просматривают отсортированный массив с обоих концов, сдвигая один из них внутрь на каждом шаге, пока left < right. Линейно, правильно и полезно для множества других приёмов. 🚀
Часто задаваемые вопросы
Урок «Два указателя в отсортированном массиве» бесплатный?
Да — полный текст урока «Два указателя в отсортированном массиве» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Два указателя в отсортированном массиве»?
Сдвигайте концы навстречу друг другу, чтобы найти цель Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Два указателя в отсортированном массиве»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Два указателя в отсортированном массиве
- Поиск пары с заданной суммой
- Удаление дубликатов на месте
- Слияние двух отсортированных последовательностей