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->2->3->4->5, то выход должен быть 3 .
Мы также можем использовать технику двух указателей в других структурах данных, подобных массивам, например 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 .