«1. Обзор

В этом руководстве мы обсудим подход с двумя указателями для решения задач, связанных с массивами и списками. Этот метод — простой и эффективный способ улучшить производительность нашего алгоритма.

2. Описание метода

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

Для решения таких проблем мы обычно начинаем с первого индекса и перебираем массив один или несколько раз в зависимости от нашей реализации. Иногда нам также приходится создавать временный массив в зависимости от требований нашей задачи.

Описанный выше подход может дать нам правильный результат, но он, скорее всего, не даст нам наиболее эффективного по времени и пространству решения.

В результате часто бывает полезно подумать, можно ли эффективно решить нашу проблему, используя подход с двумя указателями.

В подходе с двумя указателями указатели ссылаются на индексы массива. Используя указатели, мы можем обрабатывать два элемента за цикл вместо одного.

Общие шаблоны в подходе с двумя указателями включают:

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

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

Теперь давайте рассмотрим несколько примеров, которые помогут нам лучше понять эту технику.

3. Сумма существует в массиве

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

Например, если наш входной массив равен [1, 1, 2, 3, 4, 6, 8, 9] и целевое значение равно 11, тогда наш метод должен возвращать значение true. Однако, если целевое значение равно 20, оно должно вернуть false.

Давайте сначала рассмотрим наивное решение: 

public boolean twoSumSlow(int[] input, int targetValue) {

    for (int i = 0; i < input.length; i++) {
        for (int j = 1; j < input.length; j++) {
            if (input[i] + input[j] == targetValue) {
                return true;
            }
        }
    }
    return false;
}

В приведенном выше решении мы дважды перебрали входной массив, чтобы получить все возможные комбинации. Мы сравнили сумму комбинации с целевым значением и вернули true, если она совпадает. Временная сложность этого решения составляет O (n ^ 2).

Теперь давайте посмотрим, как здесь можно применить технику двух указателей: 

public boolean twoSum(int[] input, int targetValue) {

    int pointerOne = 0;
    int pointerTwo = input.length - 1;

    while (pointerOne < pointerTwo) {
        int sum = input[pointerOne] + input[pointerTwo];

        if (sum == targetValue) {
            return true;
        } else if (sum < targetValue) {
            pointerOne++;
        } else {
            pointerTwo--;
        }
    }

    return false;
}

Поскольку массив уже отсортирован, мы можем использовать два указателя. Один указатель начинается с начала массива, а другой указатель начинается с конца массива, а затем мы складываем значения по этим указателям. Если сумма значений меньше целевого значения, мы увеличиваем левый указатель, а если сумма выше целевого значения, мы уменьшаем правый указатель.

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

4. Повернуть массив на k шагов

Задача: Дан массив, повернуть массив вправо на k шагов, где k неотрицательно. Например, если наш входной массив равен [1, 2, 3, 4, 5, 6, 7], а k равно 4, то вывод должен быть [4, 5, 6, 7, 1, 2, 3].

Мы можем решить эту проблему, снова имея два цикла, которые сделают временную сложность O (n ^ 2), или используя дополнительный временный массив, но это сделает пространственную сложность O (n).

Вместо этого давайте решим это, используя метод двух указателей: 

public void rotate(int[] input, int step) {
    step %= input.length;
    reverse(input, 0, input.length - 1);
    reverse(input, 0, step - 1);
    reverse(input, step, input.length - 1);
}

private void reverse(int[] input, int start, int end) {
    while (start < end) {
        int temp = input[start];
        input[start] = input[end];
        input[end] = temp;
        start++;
        end--;
    }
}

В приведенных выше методах мы несколько раз переворачиваем секции входного массива на месте, чтобы получить требуемый результат. Для обращения секций мы использовали подход с двумя указателями, при котором замена элементов производилась на обоих концах секции массива.

В частности, мы сначала переворачиваем все элементы массива. Затем мы меняем местами первые k элементов, а затем меняем местами остальные элементы. Временная сложность этого решения — O(n), а пространственная сложность — O(1).

5. Средний элемент в LinkedList

«Проблема: для одного LinkedList найти его средний элемент. Например, если наш входной LinkedList равен 1-\u003e2-\u003e3-\u003e4-\u003e5, то на выходе должно быть 3.

Мы также можем использовать технику двух указателей в других структурах данных, подобных массивам, например a LinkedList: 

public <T> T findMiddle(MyNode<T> head) {
    MyNode<T> slowPointer = head;
    MyNode<T> fastPointer = head;

    while (fastPointer.next != null && fastPointer.next.next != null) {
        fastPointer = fastPointer.next.next;
        slowPointer = slowPointer.next;
    }
    return slowPointer.data;
}

В этом подходе мы просматриваем связанный список, используя два указателя. Один указатель увеличивается на единицу, а другой увеличивается на два. Когда быстрый указатель достигнет конца, медленный указатель окажется в середине связанного списка. Временная сложность этого решения — O(n), а пространственная сложность — O(1).

6. Заключение

В этой статье мы обсудили, как мы можем применить метод двух указателей, увидев несколько примеров, и рассмотрели, как он повышает эффективность нашего алгоритма.

Код из этой статьи доступен на Github.