Техника двух указателей

Два указателя — это чрезвычайно распространенная техника, используемая для решения задач с массивами и строками. Она включает использование двух целочисленных переменных, которые перемещаются по итерируемому объекту. В этой статье мы сосредоточимся на массивах и строках. Это означает, что у нас будут два целых числа, обычно называемые чем-то вроде i и j, или left и right, которые представляют собой индексы массива или строки.

Существует несколько способов реализации двух указателей. Для начала давайте рассмотрим следующий метод:

Указатели на краях входных данных

Перемещаем их навстречу друг другу, пока они не встретятся.

Перевод этой идеи в инструкции:

1. Установите один указатель на первый индекс (0), а другой указатель на последний индекс (input.length - 1).
2. Используйте цикл while, пока указатели не станут равны друг другу.
3. На каждой итерации цикла перемещайте указатели навстречу друг другу. Это означает либо инкрементировать указатель, который начинался с первого индекса, либо декрементировать указатель, который начинался с последнего индекса, или и то, и другое. Решение о том, какие указатели двигать, будет зависеть от задачи, которую мы пытаемся решить.

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. left++
            2. right--
            3. Both left++ and right--

Сила этой техники заключается в том, что у нас никогда не будет больше чем O(n) итераций для цикла while, потому что указатели начинают с расстояния n друг от друга и на каждой итерации перемещаются как минимум на один шаг ближе. Поэтому, если мы можем удерживать работу внутри каждой итерации на уровне O(1), эта техника приведет к линейному времени выполнения, что обычно является наилучшим возможным временем выполнения.

Давайте рассмотрим несколько примеров
https://leetcode.com/problems/valid-palindrome/description/
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Одновременное движение по разным массивам

Преобразование этой идеи в инструкции:

1. Создайте два указателя, по одному для каждого итерируемого объекта. Каждый указатель должен начинаться с первого индекса.
2. Используйте цикл while, пока один из указателей не достигнет конца своего итерируемого объекта.
3. На каждой итерации цикла перемещайте указатели вперед. Это означает инкрементировать либо один из указателей, либо оба указателя. Решение о том, какие указатели двигать, будет зависеть от задачи, которую мы пытаемся решить.
4. Поскольку наш цикл while остановится, когда один из указателей достигнет конца, другой указатель не будет находиться в конце своего итерируемого объекта, когда цикл завершится. Иногда нам нужно пройти через все элементы - если это так, вам нужно будет написать дополнительный код, чтобы убедиться, что оба итерируемых объекта исчерпаны.

function fn(arr1, arr2):
    i = j = 0
    while i < arr1.length AND j < arr2.length:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. i++
            2. j++
            3. Both i++ and j++

    // Step 4: make sure both iterables are exhausted
    // Note that only one of these loops would run
    while i < arr1.length:
        Do some logic here depending on the problem
        i++

    while j < arr2.length:
        Do some logic here depending on the problem
        j++

Давайте рассмотрим несколько примеров
https://leetcode.com/problems/merge-sorted-array/description/
https://leetcode.com/problems/is-subsequence/description/

Заключительные замечания

Помните, что описанные здесь методы — это всего лишь руководящие принципы.
Например, в первом методе мы начинали указатели с первого и последнего индексов, но иногда вы можете столкнуться с задачей, где указатели начинают с других индексов.
Во втором методе мы перемещали два указателя по двум разным входным данным. Иногда будет только один входной массив/строка, но мы все равно инициализируем оба указателя на первом индексе и перемещаем их вперед.

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

Задачи

https://leetcode.com/problems/reverse-string/description/
https://leetcode.com/problems/squares-of-a-sorted-array/description/
https://leetcode.com/problems/reverse-words-in-a-string-iii/
https://leetcode.com/problems/reverse-only-letters/description/
https://leetcode.com/problems/minimum-common-value/description/
https://leetcode.com/problems/reverse-prefix-of-word/description/