В чём особенность алгоритма двух указателей?

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

Основные варианты

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

Пример: поиск пары с заданной суммой

В отсортированном массиве нужно найти два числа, сумма которых равна target. Вместо двух вложенных циклов ставим указатели на начало и конец.

function twoSumSorted(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }

  return [];
}

console.log(twoSumSorted([1, 2, 4, 7, 11], 9)); // [1, 3]

Здесь на каждом шаге мы либо увеличиваем левый указатель, либо уменьшаем правый. Количество итераций не превышает длины массива, поэтому сложность O(n), а память O(1).

Где применяется

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

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

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