В предыдущем уроке мы разобрали бинарный поиск — элегантный O(log n), но работающий только с поиском одного элемента в отсортированном массиве. А что, если задача сложнее? Не «найди элемент», а «найди пару элементов с определённым свойством»? Или «обработай массив на месте, без лишней памяти»? Тут бинарный поиск бессилен, а наивный перебор — слишком медленный. Время познакомиться с приёмом, который превращает O(n²) в O(n).

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

Наивный подход — перебрать все возможные пары. Берём первый товар, пробуем каждый второй. Потом берём второй, пробуем каждый оставшийся. И так далее:

int[] prices = { 150, 200, 350, 500, 650, 800, 900 };
int budget = 1000;

for (int i = 0; i < prices.Length; i++)
    for (int j = i + 1; j < prices.Length; j++)
        if (prices[i] + prices[j] == budget)
            Console.WriteLine($"{prices[i]} + {prices[j]} = {budget}");
// Выведет: 150 + 850... а нет, 850 нет в массиве.
// Выведет: 200 + 800 = 1000, 350 + 650 = 1000

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

Но стоп. Массив отсортирован. Мы уже знаем из урока про бинарный поиск: порядок — это сила. Порядок позволяет срезать углы. И здесь есть приём, ещё проще бинарного поиска. Представьте длинный школьный коридор. По стенам развешаны таблички с числами — по возрастанию слева направо. У левого входа стоит Алиса, у правого — Боб. Каждый видит число на ближайшей табличке. Алиса — самое маленькое, Боб — самое большое.

Они складывают свои числа. Сумма слишком большая? Боб делает шаг влево — к числу поменьше. Слишком маленькая? Алиса шагает вправо — к числу побольше. Ровно то, что нужно? Победа! А если встретились и ничего не нашли — значит, подходящей пары просто не существует.

Сколько шагов они сделают в самом плохом случае? Алиса может сделать максимум n шагов вправо. Боб — максимум n шагов влево. Итого — не больше n шагов суммарно. O(n). Два вложенных цикла заменены одним проходом. Нет — математика.

Реализуем задачу с прайс-листом. Два указателя стартуют с краёв: left — на самом дешёвом товаре, right — на самом дорогом:

int[] prices = { 150, 200, 350, 500, 650, 800, 900 };
int budget = 1000;

int left = 0;
int right = prices.Length - 1;

while (left < right)
{
    int sum = prices[left] + prices[right];

    if (sum == budget)
    {
        Console.WriteLine($"{prices[left]} + {prices[right]} = {budget}");
        left++;      // Ищем следующую пару
        right--;
    }
    else if (sum < budget)
    {
        left++;      // Сумма маленькая — сдвигаем левый вправо
    }
    else
    {
        right--;     // Сумма большая — сдвигаем правый влево
    }
}
// Выведет: 200 + 800 = 1000, 350 + 650 = 1000

Разберём, почему это работает. Это важно — не просто «так сказали», а понять логику доказательства. Допустим, sum < budget. Мы двигаем left вправо. Почему не right влево?

Потому что right уже указывает на максимально возможный элемент. Если даже с ним сумма мала — с любым элементом левее будет ещё меньше. Значит, текущий prices[left] не может быть частью ответа ни с каким другим элементом. Его можно смело отбросить.

Аналогично для sum > budget: текущий prices[right] слишком большой даже в паре с минимальным элементом — отбрасываем его, сдвигая right влево.

Вот почему важна сортировка. Без неё мы не можем утверждать, что слева — минимум, а справа — максимум. Без неё сдвиг указателя ничего не гарантирует. Порядок — ключ ко всему. То, что мы только что разобрали, называется встречные указатели (converging pointers) — они стартуют с противоположных концов и двигаются навстречу друг другу. Но есть второй, не менее полезный тип: попутные указатели (same-direction pointers) — оба бегут в одну сторону, просто с разной скоростью.

Разберём классический пример. Задача: убрать дубликаты из отсортированного массива. Точнее — переместить уникальные элементы в начало и вернуть их количество. Важное условие: сделать это на месте, без создания нового массива. Эта задача — прямо с LeetCode (задача #26), и она всплывает на собеседованиях с завидной регулярностью.

Наивный подход — создать новый массив и копировать только уникальные элементы. Работает, но требует O(n) дополнительной памяти. А если массив занимает гигабайт? Два гигабайта в памяти — расточительство.

Идея с попутными указателями: один указатель (slow) отмечает позицию, куда записывать следующий уникальный элемент. Второй (fast) бежит вперёд и ищет новые уникальные значения. Когда fast находит элемент, отличающийся от того, на который смотрит slow, — это новый уникальный элемент. Записываем его на позицию slow + 1.

int RemoveDuplicates(int[] arr)
{
    if (arr.Length == 0) return 0;

    int slow = 0;                        // Позиция последнего уникального

    for (int fast = 1; fast < arr.Length; fast++)
    {
        if (arr[fast] != arr[slow])      // Нашли новый уникальный элемент
        {
            slow++;
            arr[slow] = arr[fast];       // Записываем его на позицию slow
        }
        // Если arr[fast] == arr[slow] — просто пропускаем дубликат
    }

    return slow + 1;                     // Количество уникальных
}

// Пример:
int[] data = { 1, 1, 2, 2, 2, 3, 4, 4, 5 };
int count = RemoveDuplicates(data);

// count = 5
// data теперь начинается с: [1, 2, 3, 4, 5, ...]
for (int i = 0; i < count; i++)
    Console.Write(data[i] + " ");
// Выведет: 1 2 3 4 5

Заметьте элегантность: fast пробегает массив ровно один раз — O(n). Дополнительная память — O(1), потому что мы модифицируем массив прямо на месте. Никаких новых массивов, никаких списков, никаких хеш-таблиц.

Посмотрим, что происходит пошагово на массиве [1, 1, 2, 2, 3]:

fast=1: arr[1]=1 == arr[slow=0]=1 → пропускаем дубликат
fast=2: arr[2]=2 != arr[slow=0]=1 → slow=1, arr[1]=2   → [1, 2, 2, 2, 3]
fast=3: arr[3]=2 == arr[slow=1]=2 → пропускаем дубликат
fast=4: arr[4]=3 != arr[slow=1]=2 → slow=2, arr[2]=3   → [1, 2, 3, 2, 3]

Результат: первые 3 элемента = [1, 2, 3], count = 3

Обратите внимание: элементы после позиции slow — мусор. Их содержимое не имеет значения, потому что мы вернули count = 3 и обязуемся читать только первые 3 элемента.

Попутные указатели — как два бегуна на дистанции. Быстрый убежал вперёд и разведывает обстановку. Медленный идёт сзади и записывает только важные находки. Вместе они за один проход обрабатывают весь массив.

Итак, у нас два типа двух указателей. Когда какой использовать?

Встречные указатели (left и right идут навстречу) — когда нужно найти пару элементов с определённым свойством. Типичные задачи: пара с заданной суммой, контейнер с максимальной водой, проверка палиндрома, разворот массива. Признак: вы ищете что-то на двух «краях» и хотите двигаться к центру.

Попутные указатели (slow и fast бегут в одном направлении) — когда нужно обработать массив на месте: убрать дубликаты, отфильтровать нули, разделить элементы по условию. Признак: один указатель «исследует», другой «записывает».

Когда стоит вообще подумать о двух указателях? Вот чеклист:

• Массив отсортирован (или его можно отсортировать без потери смысла).
• Нужно найти пару элементов с определённым свойством — суммой, разностью, произведением.
• Нужно что-то сделать на месте — без дополнительного массива.
• Задача решается двумя вложенными циклами, но у вас интуитивное ощущение: «Это же O(n²), должно быть лучше!»
• В массиве есть монотонность: если сдвинуть один указатель, то становится ясно, куда двигать второй.

Последний пункт — ключевой. Два указателя работают благодаря монотонности. Сдвиг left вправо увеличивает левый элемент (массив отсортирован). Сдвиг right влево уменьшает правый. Это даёт однозначное правило: сумма мала — двигай left, велика — двигай right. Без этой однозначности два указателя не работают.

Сравним три подхода к задаче «найти пару с заданной суммой»:

Видите? Два указателя дают идеальную комбинацию: линейное время и константная память. HashSet тоже работает за O(n), но тратит O(n) памяти — для миллиарда элементов это гигабайты. А два указателя обходятся двумя переменными.

Ещё один классический пример встречных указателей — разворот массива. Два указателя стартуют с краёв, меняют элементы местами и движутся навстречу:

char[] chars = "hello".ToCharArray();
int left = 0, right = chars.Length - 1;

while (left < right)
{
    char temp = chars[left];
    chars[left] = chars[right];
    chars[right] = temp;
    left++;
    right--;
}

Console.WriteLine(new string(chars));  // "olleh"

Тот же паттерн: стартуем с краёв, двигаемся к центру, на каждом шаге делаем полезную работу. Три строчки логики — и массив развёрнут за O(n) с O(1) памяти. Никаких Array.Reverse() — чистое понимание алгоритма.

Подведём итог. Метод двух указателей — это не конкретный алгоритм, а паттерн мышления. Увидев задачу на массив, спрашивайте себя: «А что если поставить два указателя и двигать их по правилам?» Часто ответ — да, это работает.

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

Two Pointers (два указателя) — приём, при котором два индекса двигаются по массиву по определённым правилам, позволяя решить задачу за O(n) вместо O(n²).

Встречные указатели (converging) — left и right стартуют с краёв и идут навстречу. Применяются для поиска пар с заданной суммой, разворота массива, проверки палиндромов.

Попутные указатели (same-direction) — slow и fast бегут в одну сторону. Применяются для удаления дубликатов, фильтрации элементов на месте.

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

Два указателя дают O(n) по времени и O(1) по памяти. Если массив не отсортирован — добавляется O(n log n) на сортировку.