Что такое two pointers?
На этой странице
Two pointers - паттерн, где два указателя движутся по массиву или строке, чтобы решить задачу за один проход или без вложенного цикла. Часто используется на отсортированных массивах, палиндромах и задачах с парами.
Вопрос
Что такое two pointers и в каких задачах применяется этот паттерн?
Базовая идея
Вместо двух вложенных циклов:
for i
for jдвигаем два индекса:
left -> <- rightTwo 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.
| left | right | nums[left] + nums[right] | Действие |
|---|---|---|---|
| 0 | 4 | 1 + 9 = 10 | нашли [0, 4] |
Чуть сложнее, target = 7:
| left | right | Сумма | Действие |
|---|---|---|---|
| 0 | 4 | 1 + 9 = 10 | больше 7, right-- |
| 0 | 3 | 1 + 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. - Палиндромы - классика.
- Главное - правило движения.