Паттерн: Два указателя

Признак в условии

• вход отсортирован
• «пара с суммой», «палиндром», «удалить на месте»
• нужно O(1) дополнительной памяти
• надо сравнивать элементы с разных концов

Идея

Два индекса вместо вложенного цикла. Навстречу - когда вход отсортирован и есть монотонность. Быстрый и медленный - когда надо писать и читать в один массив или искать середину.

Шаблон

let l = 0, r = nums.length - 1;
while (l < r) {
  const sum = nums[l] + nums[r];
  if (sum === target) return [l, r];
  if (sum < target) l++;     // нужно больше
  else r--;                  // нужно меньше
}

let write = 0;                       // чтение/запись
for (let read = 0; read < nums.length; read++) {
  if (keep(nums[read])) nums[write++] = nums[read];
}
return write;

Сложность

Время O(n), память O(1). Если нужна сортировка - O(n log n).

Частые ошибки

• внутренние циклы пропуска не проверяют l < r и уходят за границу
• двигают не тот указатель (в задаче про воду - надо двигать меньшую сторону)
• забыт пропуск дублей, из-за чего в ответе повторяющиеся тройки

Мнемоника

«Отсортировано - значит с двух концов»

Не путать с

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

Задачи на этот паттерн

• пара с суммой в отсортированном массиве
• палиндром двумя указателями
• сдвинуть нули в конец
• удалить дубли на месте
• контейнер с водой
• тройки с нулевой суммой
• сортировка трёх значений
• квадраты отсортированного массива
• строки с забоем
• слияние в первый массив

Суть

Два индекса двигаются по массиву по правилу, и каждый шаг отбрасывает варианты, которые точно не дадут ответ. Вместо перебора пар за O(n²) получаем один проход O(n) и O(1) памяти.

Как распознать по условию

• массив отсортирован или его можно отсортировать;
• ищем пару (тройку) с заданной суммой или разностью;
• проверка палиндрома, сравнение концов;
• «на месте», «без дополнительной памяти»: удалить дубликаты, переместить нули;
• слияние или пересечение двух отсортированных массивов.

Схема 1: встречные указатели

function pairSum(arr, target) { // arr отсортирован
  let l = 0, r = arr.length - 1;
  while (l < r) {
    const sum = arr[l] + arr[r];
    if (sum === target) return [l, r];
    if (sum < target) l++;   // нужно больше
    else r--;                // нужно меньше
  }
  return null;
}

Почему не теряем ответ: если сумма меньше target, у arr[l] нет пары среди оставшихся, его можно выбросить.

Схема 2: медленный и быстрый

Быстрый читает каждый элемент, медленный указывает, куда писать следующий «хороший».

function removeDuplicates(arr) { // отсортирован
  if (arr.length === 0) return 0;
  let w = 1;
  for (let r = 1; r < arr.length; r++) {
    if (arr[r] !== arr[w - 1]) arr[w++] = arr[r];
  }
  return w; // arr[0..w) уникальны
}

Инвариант: arr[0..w) уже готовый ответ.

Схема 3: по двум массивам

function merge(a, b) {
  const res = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    res.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  return res.concat(a.slice(i), b.slice(j));
}

Если нужно слить в первый массив с буфером в конце, идём с конца, чтобы не затирать данные.

Сложность

O(n) (или O(n + m) для двух массивов), память O(1). Если нужна сортировка, добавь O(n log n). 3Sum: сортировка + цикл + два указателя = O(n²).

Ловушки

• while (l <= r) вместо l < r в задаче о паре: элемент сложится сам с собой.
• В 3Sum забыть пропускать одинаковые значения: дубликаты троек.
• Применять к неотсортированному массиву без сортировки.
• После сортировки потерять исходные индексы, если их нужно вернуть.

Что спросят на собесе

• Почему два указателя не пропускают ответ?
• Как решить 3Sum и почему O(n²)?
• Как удалить дубликаты на месте?
• Когда лучше Map, а когда два указателя?