pattern heroPT–23LeetCode Extension

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

Решаем задачу двумя указателями: два места в данных, которые двигаются по правилу. Куда они идут, зависит от задачи. Главное, что данные проходятся один раз, а не перебираются все пары.

Вариант
P02 Два указателяНавстречу · 1×

Пример задачи: найти индексы двух чисел с суммой 17 в отсортированном массиве [2, 3, 5, 8, 9, 12, 16, 19].

0213253849512616719left
ещё возможныпроверяемая параотброшенынайденная пара

left — на самом маленьком числе, 2

left = 0right = –sum = –
01/26
сначала · назад · пуск · шаг
Скорость
1function pairWithSum(nums, target):
2 left = 0
3 right = len(nums) - 1
4 while left < right:
5 sum = nums[left] + nums[right]
6 if sum < target:
7 left = left + 1
8 else if sum > target:
9 right = right - 1
10 else:
11 return [left, right]

← → шаг · пробел — пауза

Как узнать

отсортированный массив и пара или тройка с заданной суммой, проверка палиндрома или что угодно, что сравнивают с двух концов.

Как решать такие задачи

  1. Сначала отсортируй вход, если исходные позиции не нужны.
  2. Поставь по указателю на каждый конец.
  3. Сравни то, что даёт пара, с целью. Мало — сдвинь левый вправо. Много — сдвинь правый влево.
  4. Остановись, когда нашёл или когда указатели встретились. Каждый сдвиг должен отбрасывать число навсегда.

Вариант: В одну сторону

То же, но оба указателя идут в одну сторону: один читает, другой отмечает, куда записать следующий нужный элемент. Так массив переписывают на месте, без второго массива.

  1. Подходит, чтобы отфильтровать или уплотнить массив на месте: убрать повторы или заданное значение, сдвинуть нули в конец, разделить по условию.
  2. read проходит каждый элемент один раз. write — индекс, куда встанет следующий оставленный элемент.
  3. Держи инвариант: всё левее write — ответ на данный момент. Если nums[read] проходит проверку, скопируй его в nums[write] (или обменяй, если остальное нужно сохранить) и сдвинь write.
  4. Когда read дойдёт до конца, write — длина ответа. Всё начиная с write — остатки.

Вариант: Два массива

То же, но указатели стоят в двух разных массивах, по одному в каждом. Сдвигаем тот, что отстал, и так сливаем или сравниваем два отсортированных массива за один проход.

  1. Подходит, когда две отсортированные последовательности нужно пройти вместе: слить, пересечь, сравнить.
  2. Поставь по указателю на каждую. На каждом шаге сравни два элемента и сдвинь тот указатель, чей элемент использовал.
  3. Если результат пишется в один из входов, заполняй его с конца, где свободное место, третьим указателем — куда писать.
  4. Так же, проходя бок о бок, проверяют, является ли одна строка подпоследовательностью другой: по длинной строке шагай всегда, по короткой — только при совпадении букв.

Где встречается

  • Поиск в интернете. Ты ищешь «кошка собака». У поисковика есть два отсортированных списка страниц: где есть «кошка» и где есть «собака». Он ставит по пальцу на начало каждого списка: номера совпали — страница подходит, не совпали — двигает палец, который отстал. Так, за один проход, ищут Lucene и Elasticsearch.
  • Базы данных. Нужно соединить таблицу заказов с таблицей клиентов по id. Обе отсортированы по id, поэтому база идёт по ним двумя указателями одновременно и склеивает строки с одинаковым id. Сравнивать каждый заказ с каждым клиентом не нужно. Это называется merge join.
  • Сортировка. Quicksort выбирает опорное число, и два указателя идут с краёв навстречу: левый ищет число больше опорного, правый — меньше, и их меняют местами. Через один проход маленькие числа слева, большие справа. Так устроена сортировка в стандартной библиотеке C++.
  • Команда comm в Unix. Сравнивает два отсортированных файла и показывает, какие строки есть только в первом, только во втором и в обоих. Идёт по файлам двумя указателями: строки совпали — общая, не совпали — сдвигает указатель на меньшей строке.