Алгоритм «Два указателя»: решаем задачи на массивы быстро и элегантно

Техническое собеседование в IT-компанию — это не экзамен на знание синтаксиса языка. Интервьюер хочет понять, умеете ли вы думать об эффективности. Именно поэтому задачи на массивы появляются в каждом втором собеседовании: они компактны, хорошо масштабируются по сложности и мгновенно показывают, знаком ли кандидат с базовыми алгоритмическими техниками.

Одна из таких техник — два указателя (two pointers). Она не требует сложной математики и не занимает больше десяти строк кода. Но именно она отделяет решение за O(n²) от решения за O(n) — и именно это замечает интервьюер.

В этой статье разберём технику на пяти классических задачах с полным кодом на Python, объясним, почему она работает, и покажем типичные ошибки, которые допускают даже опытные разработчики.

Что такое техника двух указателей

Идея проста: вместо того чтобы перебирать все пары элементов вложенным циклом (O(n²)), мы заводим два индекса — левый и правый — и двигаем их навстречу друг другу или в одном направлении в зависимости от условия задачи. Это позволяет обойти массив за один проход — O(n).

Техника применима, когда:

• массив отсортирован (или его можно отсортировать без потери смысла задачи);
• нужно найти пару, тройку или подмассив с определённым свойством;
• задача сводится к сужению диапазона поиска на основе сравнения элементов.

Существует два основных варианта:

1. Встречные указатели — левый стартует с начала, правый с конца, движутся навстречу.
2. Скользящее окно / быстрый и медленный указатель — оба движутся в одном направлении, но с разной скоростью или условием сдвига.

Разберём оба варианта на конкретных задачах.

Задача 1. Два числа с заданной суммой (Two Sum II)

Условие

Дан отсортированный массив целых чисел и целевое число target. Найти индексы двух элементов, сумма которых равна target. Индексы возвращаются с единицы (1-based).

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

def two_sum_naive(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]

Сложность: O(n²) по времени. На массиве из 10 000 элементов — уже 50 миллионов итераций.

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

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1   # сумма слишком мала — берём большее число слева
        else:
            right -= 1  # сумма слишком велика — берём меньшее число справа

    return []  # решения нет

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

Сложность: O(n) по времени, O(1) по памяти.

Задача 2. Разворот строки на месте (Reverse String)

Условие

Развернуть массив символов in-place, не используя дополнительную память.

Решение

def reverse_string(s):
    left, right = 0, len(s) - 1

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

Классический пример встречных указателей. Мы меняем крайние элементы местами и двигаемся к центру. Когда left >= right — массив развёрнут.

s = ['h', 'e', 'l', 'l', 'o']
reverse_string(s)
print(s)  # ['o', 'l', 'l', 'e', 'h']

Сложность: O(n) по времени, O(1) по памяти. Никаких срезов s[::-1] — здесь мы работаем in-place, что принципиально важно в задачах с ограничением по памяти.

Задача 3. Контейнер с наибольшим количеством воды (Container With Most Water)

Условие

Дан массив высот height, где height[i] — высота вертикальной линии в точке i. Найти два индекса i и j (i < j), при которых площадь «контейнера» (минимальная из двух высот, умноженная на расстояние между ними) максимальна.

Решение

def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # Ширина контейнера
        width = right - left
        # Высота ограничена меньшей из двух стенок
        current_area = min(height[left], height[right]) * width
        max_water = max(max_water, current_area)

        # Сдвигаем указатель со стороны меньшей высоты
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

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

print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Задача 4. Три числа с нулевой суммой (3Sum)

Условие

Найти все уникальные тройки в массиве, сумма элементов которых равна нулю.

Это одна из самых частых задач на собеседованиях в крупные компании. Она интересна тем, что требует комбинации сортировки, двух указателей и аккуратной обработки дубликатов.

Решение

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Пропускаем дубликаты для первого элемента
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Пропускаем дубликаты для второго и третьего элементов
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1

            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1, -1, 2], [-1, 0, 1]]

Типичная ошибка: забыть про обработку дубликатов. Без пропуска повторяющихся элементов алгоритм вернёт одинаковые тройки несколько раз. Обратите внимание на три места, где мы проверяем дубликаты: для i, для left и для right.

Сложность: O(n²) — сортировка O(n log n) плюс вложенный цикл O(n²). Это оптимально для данной задачи: доказано, что лучше O(n²) для 3Sum не достичь без дополнительных ограничений.

Задача 5. Удаление дубликатов из отсортированного массива (Remove Duplicates)

Условие

Дан отсортированный массив. Удалить дубликаты in-place так, чтобы каждый элемент встречался только один раз. Вернуть количество уникальных элементов.

Здесь оба указателя движутся в одном направлении — это второй классический паттерн техники.

Решение

def remove_duplicates(nums):
    if not nums:
        return 0

    # slow — граница уникальных элементов
    # fast — сканирует весь массив
    slow = 0

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

nums = [1, 1, 2, 3, 3, 4]
k = remove_duplicates(nums)
print(k)         # 4
print(nums[:k])  # [1, 2, 3, 4]

Как это работает: slow отслеживает позицию последнего записанного уникального элемента. fast бежит вперёд. Как только fast находит элемент, отличный от nums[slow], мы продвигаем slow и записываем туда новый уникальный элемент. Дубликаты просто перезаписываются или остаются за границей slow.

Это паттерн «медленный и быстрый указатель» — он же используется для поиска цикла в связном списке (алгоритм Флойда), но это уже тема отдельной статьи.

Когда техника двух указателей не работает

Важно понимать ограничения метода, чтобы не применять его там, где он не подходит.

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

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

Связные списки с произвольным доступом. Для связных списков два указателя работают только в специфических сценариях (поиск середины, цикл), потому что нет индексного доступа к элементам.

Как готовиться к собеседованию с этой техникой

Знание паттерна — это половина дела. На собеседовании важно уметь объяснить, почему вы выбрали именно этот подход. Типичная структура ответа:

1. Назвать наивное решение и его сложность.
2. Объяснить, какое свойство задачи позволяет применить два указателя.
3. Показать инвариант: что остаётся истинным на каждом шаге цикла.
4. Разобрать граничные случаи: пустой массив, один элемент, все элементы одинаковые.

Для систематической подготовки к таким задачам стоит изучить не только паттерны, но и математическую основу их корректности. Если вы хотите разобраться в этом структурированно — курс «Алгоритмы и Структуры Данных на Python» охватывает именно этот пласт: от анализа сложности до реализации классических алгоритмов с разбором типичных задач с интервью.

Сводная таблица разобранных задач

Вывод

Техника двух указателей — один из тех инструментов, которые после изучения начинаешь замечать повсюду. Она лежит в основе десятков задач на LeetCode, регулярно встречается на собеседованиях в компании уровня FAANG и российских IT-лидеров, и при этом остаётся концептуально простой.

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

Следующий шаг — практика. Решите каждую из пяти задач самостоятельно, без подглядывания в код. Затем попробуйте задачи-вариации: Trapping Rain Water, Sort Colors (флаг Нидерландов), Minimum Size Subarray Sum. Если хочется двигаться по структурированной программе с разбором теории и задач — курс «Алгоритмы и Структуры Данных на Python» может стать хорошей точкой опоры для этой подготовки.