8.1 Метод двух указателей¶

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

Такой подход особенно полезен в задачах, где нужно поддерживать текущий отрезок массива, проверять его свойства и быстро переходить к следующему кандидату. Ниже разберём два классических применения этого метода.

Поиск подотрезка с заданной суммой¶

Постановка задачи¶

Дан массив из n положительных чисел и число x. Нужно определить, существует ли подотрезок, сумма элементов которого равна x.

Рассмотрим пример:

2 1 4 3 2 1 5

При x = 7 подходит подотрезок:

2 1 4 3 2 1 5
    └─┘
     4+3 = 7

Именно такие подряд идущие элементы нас и интересуют.

Идея¶

Будем поддерживать текущий отрезок [l, r] и его сумму.

• Если сумма слишком мала, расширяем отрезок вправо.
• Если сумма слишком велика или уже невыгодна, сдвигаем левую границу.
• Если сумма стала равна x, решение найдено.

Поскольку все числа положительные, расширение вправо только увеличивает сумму, а сдвиг левой границы только уменьшает её. Это и делает метод корректным.

Наглядная схема¶

flowchart LR
    A["Начинаем с l = 0, r = 0, sum = 0"] --> B{"sum < x?"}
    B -- Да --> C["Двигаем r вправо и добавляем a[r]"]
    B -- Нет --> D{"sum == x?"}
    D -- Да --> E["Подотрезок найден"]
    D -- Нет --> F["Вычитаем a[l] и двигаем l вправо"]
    C --> B
    F --> B

Пример работы¶

Пусть массив:

2 1 4 3 2 1 5

и x = 7.

Сначала берём пустой отрезок. Затем расширяем его вправо:

• 2, сумма 2
• 2 1, сумма 3
• 2 1 4, сумма 7

Мы сразу нашли ответ.

Если бы сумма стала больше 7, мы начали бы убирать элементы слева, пока она снова не стала бы не больше 7.

Код на C++¶

int l = 0, sum = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum > x) {
        sum -= a[l];
        l++;
    }
    if (sum == x) {
        cout << "FOUND\n";
        return;
    }
}
cout << "NOT FOUND\n";

Почему это работает за O(n)¶

На первый взгляд может показаться, что внутренний цикл while делает алгоритм квадратичным. Но это не так.

Каждый элемент массива:

• не более одного раза добавляется в сумму правым указателем;
• не более одного раза удаляется из суммы левым указателем.

То есть оба указателя за всё время работы проходят массив не более одного раза. Поэтому суммарная сложность равна:

O(n)

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

Важное замечание¶

Этот подход в таком виде работает именно для массива из положительных чисел. Если в массиве есть отрицательные элементы, сумма перестаёт изменяться предсказуемо, и метод уже нельзя применять напрямую.

Задача 2SUM¶

Постановка задачи¶

Дан массив чисел и число x. Нужно найти два элемента массива, сумма которых равна x, либо сообщить, что такой пары нет.

Например, для массива

1 3 4 6 8 10

и x = 14 ответ существует: 4 + 10 = 14.

Идея¶

Сначала отсортируем массив. После этого поставим:

• левый указатель в начало массива;
• правый указатель в конец массива.

Дальше будем смотреть на сумму двух выбранных элементов:

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

Наглядная схема¶

flowchart LR
    A["Отсортировать массив"] --> B["Поставить l в начало, r в конец"]
    B --> C{"a[l] + a[r] == x?"}
    C -- Да --> D["Пара найдена"]
    C -- Нет --> E{"a[l] + a[r] < x?"}
    E -- Да --> F["l++"]
    E -- Нет --> G["r--"]
    F --> C
    G --> C

Пример работы¶

Пусть массив после сортировки равен:

1 3 4 6 8 10

Ищем сумму 14.

1. Берём 1 и 10, получаем 11 — мало.
2. Сдвигаем левый указатель: берём 3 и 10, получаем 13 — всё ещё мало.
3. Ещё раз сдвигаем левый указатель: берём 4 и 10, получаем 14.

Ответ найден.

Код на C++¶

sort(a.begin(), a.end());

int l = 0, r = n - 1;
while (l < r) {
    int s = a[l] + a[r];
    if (s == x) {
        cout << a[l] << " " << a[r] << "\n";
        return;
    }
    if (s < x) l++;
    else r--;
}

cout << "NO PAIR\n";

Сложность¶

Сортировка занимает:

O(n log n)

После этого указатели движутся навстречу друг другу не более чем по n шагов суммарно, то есть сам проход работает за:

O(n)

Итоговая сложность:

O(n log n)

Почему метод двух указателей так важен¶

Этот приём часто оказывается проще и быстрее, чем более тяжёлые структуры данных. Он особенно полезен, когда:

• нужно анализировать отрезки массива;
• элементы можно упорядочить сортировкой;
• границы текущего ответа можно двигать только вперёд;
• важно получить линейное или почти линейное решение.

Во многих задачах метод двух указателей — это первый инструмент, о котором стоит подумать.

Идея амортизированного анализа здесь¶

Хотя на некоторых шагах один из указателей может двигаться несколько раз подряд, суммарное число всех таких движений ограничено. Мы не оцениваем каждый шаг отдельно как «дорогой» или «дешёвый», а смотрим на полную стоимость всех операций за весь алгоритм.

Именно поэтому:

• задача о подотрезке с заданной суммой решается за O(n);
• задача 2SUM после сортировки решается за O(n log n).

Краткий вывод¶

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

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