re:re:actable
Урок 013 минуты чтения

Что такое two pointers?

На этой странице
Кратко

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

Вопрос

Что такое two pointers и в каких задачах применяется этот паттерн?

Базовая идея

Вместо двух вложенных циклов:

for i
  for j

двигаем два индекса:

left ->          <- right

Two sum на sorted array

function twoSumSorted(nums: number[], target: number): [number, number] | null {
  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 null
}

Time O(n), space O(1).

Пример: nums = [1, 3, 4, 6, 9], target = 10.

leftrightnums[left] + nums[right]Действие
041 + 9 = 10нашли [0, 4]

Чуть сложнее, target = 7:

leftrightСуммаДействие
041 + 9 = 10больше 7, right--
031 + 6 = 7нашли [0, 3]

Почему можно сдвигать указатель и ничего не потерять? Если nums[left] + nums[right] больше target, то nums[right] слишком большой для пары с любым элементом от left и правее: все они не меньше nums[left], значит суммы будут еще больше. Поэтому nums[right] можно навсегда исключить. Аналогично, если сумма меньше target, nums[left] слишком маленький для любой оставшейся пары. Каждый шаг исключает один элемент, поэтому шагов не больше n.

Это рассуждение работает только потому, что массив отсортирован.

Проверка палиндрома

function isPalindrome(s: string): boolean {
  let left = 0
  let right = s.length - 1
 
  while (left < right) {
    if (s[left] !== s[right]) return false
    left++
    right--
  }
 
  return true
}

Когда узнавать паттерн?

  • массив отсортирован;
  • нужно найти пару;
  • нужно сравнивать начало и конец;
  • нужно удалить дубликаты in-place;
  • нужно сжать строку/массив;
  • brute force проверяет пары O(n^2).

Что отвечать на собеседовании?

Two pointers использует два индекса, которые двигаются по input. Он часто заменяет вложенный перебор пар на линейный проход, если есть порядок или понятное правило движения указателей. Например, в sorted two sum сумма меньше target - двигаем left, больше target - двигаем right.

Что важно помнить: частые ошибки

  • Применять two pointers к неотсортированному массиву без основания.
  • Не доказывать, почему можно двигать указатель.
  • Ошибаться в условии left < right.
  • Забывать edge cases пустой строки/массива.
  • Двигать оба указателя сразу, когда нужно один.

Мини-шпаргалка

  • Два индекса.
  • Часто left/right.
  • Хорош для sorted arrays.
  • Убирает O(n^2) pairs.
  • Палиндромы - классика.
  • Главное - правило движения.

Документация

LeetCode: Two Pointers problems.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам