Метод двух указателей: как ускорить алгоритмы с O(n²) до O(n)

Вы когда-нибудь смотрели на задачу с собеседования и чувствовали, что пытаетесь собрать кубик Рубика с завязанными глазами? Недавно я пришёл на мок-интервью, полный уверенности, и получил вопрос: «Дан отсортированный массив, найдите два числа, сумма которых равна target». Моя первая мысль? Полный перебор: два вложенных цикла, O(n²), и молиться, чтобы тесты были маленькими. Я написал код, запустил — и смотрел, как таймер тикает, пока решение тормозило на больших данных. Интервьюер поднял бровь, а в голове заиграла музыка из «Звёздных войн». Мне нужен был лучший способ — что-то элегантное, как удар световым мечом.

Этот момент запустил моё путешествие в мир метода двух указателей. Это не просто трюк, а сдвиг мышления, который превращает казалось бы невозможные O(n²) задачи в линейные победы.

Почему два указателя работают: главная идея

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

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

Пример 1: Two Sum II (отсортированный массив)

Задача: дан отсортированный массив numbers и target, вернуть индексы двух чисел, дающих в сумме target (индексация с 1).

Наивное решение (O(n²))

def two_sum_brute(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]  # индексация с 1
    return []

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

Решение методом двух указателей (O(n))

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        cur = numbers[left] + numbers[right]
        if cur == target:
            return [left + 1, right + 1]  # индексация с 1
        if cur < target:
            left += 1  # нужна бОльшая сумма
        else:
            right -= 1  # нужна меньшая сумма
    return []

Почему это работает: отсортированный порядок гарантирует, что движение left вправо только увеличивает сумму, а right влево — уменьшает. Мы никогда не пропускаем подходящую пару, потому что любая отброшенная пара заведомо не может дать target.

Частая ошибка: забыть сдвинуть указатели после несовпадения. Если двигать только одну сторону при cur == target (или не двигать вообще при cur != target), вы либо пропустите ответ, либо зациклитесь. Всегда сдвигайте указатель, который толкает сумму к target.

Пример 2: Контейнер с наибольшим количеством воды

Задача: дан массив неотрицательных целых чисел (высоты линий), найдите две линии, которые вместе с осью X образуют контейнер, вмещающий максимум воды.

Наивное решение (O(n²))

def max_area_brute(height):
    max_water = 0
    n = len(height)
    for i in range(n):
        for j in range(i + 1, n):
            water = min(height[i], height[j]) * (j - i)
            max_water = max(max_water, water)
    return max_water

Снова двойные циклы убивают производительность на больших массивах.

Решение методом двух указателей (O(n))

def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        # площадь ограничена более короткой линией
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)
        # двигаем указатель у более короткой линии
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

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

Частая ошибка: двигать оба указателя или двигать указатель у более высокой линии. Это может пропустить оптимальный контейнер. Придерживайтесь правила: всегда двигайте указатель у более короткой линии.

Почему стоит освоить метод двух указателей

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

Плюс, уверенность, которую вы получаете, когда выдаёте O(n) решение на месте, замечают интервьюеры. Вы чувствуете, что отразили выстрел бластера световым мечом.

Ваша очередь

Вот задание, чтобы закрепить навык:

Дан отсортированный массив, найдите количество уникальных троек, сумма которых равна нулю (классическая задача 3‑Sum). Попробуйте решить её комбинацией сортировки и метода двух указателей: сначала зафиксируйте один элемент, затем ищите пару двумя указателями. Опубликуйте своё решение или возникшие трудности в комментариях — мне будет интересно посмотреть, как вы справитесь!

Удачи, и пусть ваши указатели всегда указывают в верном направлении. 🚀