Два указателя

Техника двух указателей (two pointers) — алгоритмический паттерн, использующий два индекса, движущихся по массиву или строке для решения задачи за O(n) вместо O(n^2).

Зачем нужно

Наивное решение многих задач на массивах требует двух вложенных циклов — O(n^2). Техника двух указателей устраняет внешний цикл, двигая два индекса навстречу или в одном направлении. Это один из самых частых паттернов на собеседованиях.

Где используется

  • Поиск пары с заданной суммой в отсортированном массиве
  • Разворот массива или строки на месте
  • Удаление дубликатов из отсортированного массива
  • Задача «трёх сумм» (3Sum)
  • Обнаружение цикла в связном списке (алгоритм Флойда)
  • Задача «контейнер с водой» (Container with Most Water)

Основной контент

Паттерн 1: встречные указатели (opposite direction)

Один указатель — с начала, второй — с конца. Движутся навстречу.

// Разворот массива на месте — O(n)
function reverse(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++; right--;
  }
  return arr;
}

// Пара с заданной суммой в отсортированном массиве — O(n)
function twoSum(sortedArr, target) {
  let left = 0, right = sortedArr.length - 1;
  while (left < right) {
    const sum = sortedArr[left] + sortedArr[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // нужно больше — двигаем левый вправо
    else right--;               // нужно меньше — двигаем правый влево
  }
  return null;
}

// twoSum([1, 2, 3, 4, 6], 6) → [1, 3] (2 + 4)

Паттерн 2: попутные указатели (same direction / fast-slow)

Оба движутся вправо, но с разной скоростью или условиями.

// Удаление дубликатов из отсортированного массива — O(n)
function removeDuplicates(arr) {
  if (!arr.length) return 0;
  let slow = 0;
  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }
  return slow + 1; // длина без дубликатов
}

// [0, 0, 1, 1, 2, 3] → [0, 1, 2, 3, ...]
// removeDuplicates([0, 0, 1, 1, 2, 3]) → 4

// Обнаружение цикла в связном списке (Floyd's algorithm)
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next()) {
    slow = slow.next();
    fast = fast.next().next();
    if (slow === fast) return true; // встретились — цикл есть
  }
  return false;
}

Паттерн 3: разделение по условию

// Переместить нули в конец — O(n), O(1) доп. памяти
function moveZeroes(arr) {
  let insertPos = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== 0) {
      arr[insertPos++] = arr[i];
    }
  }
  while (insertPos < arr.length) arr[insertPos++] = 0;
  return arr;
}
// [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]

Когда применять

Массив/строка + нужна пара/тройка элементов → Встречные указатели
Отсортированный массив + условие на сумму   → Встречные указатели
Удаление/сжатие дубликатов в массиве       → Попутные (fast/slow)
Обнаружение цикла в связном списке          → Fast/slow (Floyd)
Скользящее окно фиксированного размера      → [[Скользящее окно]]

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

  • Применять к неотсортированному массиву там, где требуется сортировка (two sum с встречными).
  • Не обновлять оба указателя — бесконечный цикл.
  • Путать с Скользящее окно: два указателя — для пар/разворота, скользящее окно — для подмассивов фиксированной или переменной длины.
  • Не обрабатывать случай пустого массива или массива из одного элемента.

Связанные темы

Ресурсы