Two pointer и его механики

Xaydarov Zafar AlamovichPRO 07 Oktabr 2026 · 6 daqiqa o‘qish 21 3

Полное руководство по алгоритму двух указателей

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

Метод двух указателей (Two Pointers) — это алгоритмический паттерн, который используется для оптимизации задач, связанных с массивами, строками или связными списками. Суть метода заключается в использовании двух переменных-индексов (указателей), которые перемещаются по структуре данных по определенным правилам.

Главная цель этого подхода — снижение временной сложности. Задачи, которые при использовании вложенных циклов (полного перебора) решаются за время O(N^2), с помощью двух указателей часто могут быть решены за линейное время O(N). Вторая особенность — экономия памяти. Алгоритм обычно требует O(1) дополнительной памяти, так как использует только две переменные для индексов.

В зависимости от задачи указатели могут двигаться навстречу друг другу, в одном направлении с разной скоростью или образовывать так называемое "скользящее окно".

---

Глава 1. Встречное движение (Указатели с разных концов)

Этот подход применяется в отсортированных массивах, когда необходимо найти пару элементов, удовлетворяющих определенному условию (чаще всего — сумме).

Задача: Дан отсортированный массив целых чисел. Необходимо найти два числа, сумма которых равна заданному значению (Target). Функция должна вернуть их индексы или значения.

Код на Python:

def two_sum_sorted(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return left, right      # Пара найдена
        elif current_sum < target:
            left += 1               # Сумма мала, нужно увеличить левое слагаемое
        else:
            right -= 1              # Сумма велика, нужно уменьшить правое слагаемое
            
    return -1, -1                   # Пара не найдена

Объяснение алгоритма:

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

---

Глава 2. Однонаправленные указатели (Скользящее окно)

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

Задача: Дан массив положительных чисел. Найти максимальную длину непрерывного подмассива (отрезка), сумма элементов которого не превышает заданное число S.

Код на Python:

def max_subarray_len(arr, S):
    left = 0
    current_sum = 0
    max_len = 0
    
    # Правый указатель проходит по каждому элементу массива ровно один раз
    for right in range(len(arr)):
        current_sum += arr[right]
        
        # Если окно стало "инвалидным" (сумма превысила S), сужаем его слева
        while current_sum > S and left <= right:
            current_sum -= arr[left]
            left += 1
            
        # Обновляем максимальную длину валидного окна
        max_len = max(max_len, right - left + 1)
        
    return max_len

Объяснение алгоритма:

Правый указатель добавляет элементы в текущую сумму, расширяя окно.
Внутренний цикл while включается только тогда, когда условие нарушено (current_sum > S). В этот момент левый указатель начинает двигаться вправо, вычитая свои элементы из суммы, пока окно снова не станет "валидным" (current_sum <= S).
Несмотря на вложенный цикл while, итоговая асимптотика равна O(N). Правый указатель смещается N раз, и левый указатель смещается максимум N раз. Итого не более 2N операций.

---

Глава 3. Быстрый и медленный указатель (Алгоритм Флойда)

Этот метод, также известный как алгоритм "Зайца и Черепахи", применяется преимущественно для работы со связными списками и графами. Оба указателя начинают с начала структуры, но двигаются с разной скоростью: медленный делает по одному шагу, быстрый — по два.

Задача: Определить, есть ли в односвязном списке цикл. Цикл возникает, если один из узлов ссылается на узел, который находится где-то позади, из-за чего обход списка становится бесконечным.

Код на Python:

# Определение узла связного списка
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head):
    if not head or not head.next:
        return False
        
    slow = head
    fast = head
    
    while fast is not None and fast.next is not None:
        slow = slow.next          # Медленный делает 1 шаг
        fast = fast.next.next     # Быстрый делает 2 шага
        
        if slow == fast:          # Указатели встретились
            return True
            
    return False                  # Быстрый достиг конца списка, цикла нет

Объяснение алгоритма:

Быстрый указатель обгоняет медленный. Если списка конечен (цикла нет), быстрый указатель просто достигнет конца (None), и алгоритм завершит работу.
Если цикл существует, быстрый указатель в какой-то момент "зайдет на второй круг" и окажется позади медленного.
Поскольку расстояние между ними на каждой итерации сокращается ровно на 1 шаг, они гарантированно окажутся в одном узле в одно и то же время.

---

Глава 4. Указатели для перезаписи (In-place модификация)

Два указателя часто применяются для изменения массива без выделения дополнительной памяти ("на месте"). Один указатель (быстрый) перебирает все элементы, а второй (медленный) указывает на позицию, куда нужно записать правильный элемент.

Задача: Дан отсортированный массив. Необходимо удалить дубликаты так, чтобы каждый уникальный элемент встречался только один раз. Функция должна изменить исходный массив и вернуть новое количество уникальных элементов.

Код на Python:

def remove_duplicates(arr):
    if not arr:
        return 0
        
    slow = 0 # Указывает на позицию последнего найденного уникального элемента
    
    # Быстрый указатель перебирает массив, начиная со второго элемента
    for fast in range(1, len(arr)):
        # Если найден новый уникальный элемент
        if arr[fast] != arr[slow]:
            slow += 1               # Сдвигаем позицию для записи
            arr[slow] = arr[fast]   # Перемещаем уникальный элемент вперед
            
    # Возвращаем длину массива уникальных элементов (индекс + 1)
    return slow + 1

Объяснение алгоритма:

Указатель slow резервирует индекс для записи уникальных значений. Изначально это нулевой индекс.
Указатель fast проходит по массиву в поисках новых элементов.
Поскольку массив отсортирован, дубликаты всегда стоят рядом. Условие arr[fast] != arr[slow] означает, что серия одинаковых чисел закончилась, и началось новое число.
В этот момент мы увеличиваем медленный указатель и перезаписываем элемент на этой позиции. Все дубликаты игнорируются, так как при их нахождении указатель slow остается на месте.
Этот метод требует строгие O(1) памяти, что является частым требованием на системных собеседованиях.