Метод двух указателей: как решать задачи за O(n)

Почему метод двух указателей — ваш новый супергерой

Вы когда-нибудь застревали на задаче с отсортированным массивом, перебирая все пары вложенными циклами, и чувствовали, что время уходит? Метод двух указателей — это техника, которая превращает решение из O(n²) в O(n), экономя ваши нервы и время на собеседованиях. В этой статье вы узнаете, как работает этот подход, и увидите его на практике с примерами кода на Python.

Суть метода двух указателей

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

Сложность: O(n) по времени и O(1) по памяти. Никаких вложенных циклов, только два индекса, сходящихся друг к другу.

Пример 1: Поиск двух чисел с заданной суммой

Задача: дан отсортированный массив целых чисел nums и целое число target. Верните true, если существуют два числа, дающие в сумме target, иначе false.

Наивное решение (перебор)

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

Время O(n²) — на собеседовании это выглядит как попытка победить дракона деревянным мечом.

Решение с двумя указателями

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return True  # нашли пару!
        if current < target:
            left += 1  # сумма слишком мала — увеличиваем
        else:
            right -= 1  # сумма слишком велика — уменьшаем
    return False

Как это работает: благодаря сортировке мы точно знаем, как повлияет перемещение каждого указателя. Мы не пропускаем возможные решения, а лишь отсекаем невозможные.

Частая ошибка: забыть условие left < right. Если разрешить left == right, можно использовать один и тот же элемент дважды, что обычно запрещено.

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

Задача: дан массив неотрицательных чисел height, где height[i] — высота вертикальной линии в точке i. Найдите две линии, которые вместе с осью X образуют контейнер, вмещающий максимум воды.

Наивное решение

def max_area_brute(height):
    max_water = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            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:
        width = right - left
        max_water = max(max_water, min(height[left], height[right]) * width)
        # Двигаем указатель на более низкой линии
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

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

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

Где ещё применить метод двух указателей

Освоив этот паттерн, вы заметите его повсюду:

• Задачи на скользящее окно (например, подстрока с уникальными символами).
• Слияние двух отсортированных списков.
• Проверка палиндрома (два указателя с концов строки).
• Удаление дубликатов из отсортированного массива.
• Задача 3Sum — комбинация двух указателей и цикла.

Код становится чище и проще в отладке, потому что намерение «ищем с двух концов» очевидно.

Практический вывод: что делать прямо сейчас

Возьмите задачу, которую вы раньше решали вложенными циклами — например, «3Sum», «Удалить дубликаты из отсортированного массива» или «Проверка палиндрома» — и перепишите её с использованием двух указателей. Замерьте время выполнения и сравните. Вы увидите, как код стал элегантнее и быстрее.

Поделитесь в комментариях своими примерами «до/после» и моментом «ага!». Пусть сила будет с вашими указателями! 🚀