«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.