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

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

Подход состоит из 3 шагов:

• Инициализация: Начальные точки. Указатели могут находиться в любом месте в зависимости от того, чего мы пытаемся достичь.
• Движение: Это определяет, как мы сходимся к решению. Указатели могут двигаться в одном направлении или в противоположном.
• Условие остановки: Это определяет, когда мы остановимся.

Палиндром

На вход дается строка, возвращается true, если эта строка является палиндромом, иначе false. Палиндром — это слово, число, фраза или другая последовательность символов, которые читаются одинаково как в обратном, так и в прямом направлении.

var isPalindrome = function(str) {
    let i = 0; 
    let j = str.length -1; 

    while(i<j){
        if(str[i] !== str[j]){
            return false;
        }

        i++; 
        j--;
    }

    return true; 
};

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

• Инициализация: в строках 2 и 3 мы определяем, где наши два указателя начнут обход, I в начале и j в конце.
• Движение: В строках 10 и 11 наши два указателя будут двигаться в противоположном направлении: первый — вперед, а второй — в обратном направлении.
• Условие остановки: обход остановится, когда i>j, потому что, поскольку я начинаю в начале, а j в конце, пока i увеличивается, а j уменьшается, в середине массива i будет больше j, и мы предполагаем, что все элементы были пройдены.

Является парной суммой:

Учитывая отсортированный массив A (отсортированный по возрастанию), содержащий N целых чисел, найдите, существует ли какая-либо пара элементов (A[i], A[j]) такая, что их сумма равна X.

Наивный подход:

Этот подход заключается в использовании двух вложенных циклов. Первый цикл будет начинаться с первого элемента массива до второго последнего. Второй цикл будет начинаться с i+1 до конца массива. Внутри второго цикла мы будем вычислять сумму текущих элементов, если их сумма равна искомому значению, мы вернем true, иначе остановим второй цикл.

function isPairSum(nums, X) {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {

      if (nums[i] + nums[j] == X) return true;

      if (nums[i] + nums[j] > X) break;
    }
  }

  return false;
}

Временная сложность этого решения составляет O(N²) из-за двух вложенных циклов.

Подход с двумя указателями:

function isPairSum2(nums, X) {
  // first pointer
  let i = 0;

  // second pointer 
  let j = nums.length - 1;
  while (i < j) {

    if (nums[i] + nums[j] == X) return true;

    else if (nums[i] + nums[j] < X) i++;

    else j--;
  }
  return false;
}

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

• Инициализация: в строках 3 и 6 происходит инициализация, первый указатель будет находиться в начале списка, а второй — в конце.
• Движение: они будут двигаться в противоположном направлении в соответствии со строками 11 и 13, если их сумма меньше значения, первый указатель будет двигаться вперед, если их сумма больше искомого значения, второй указатель будет двигаться назад.
• Условие остановки: обход остановится, когда первый указатель опередит второй.

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

Рассмотрим другую задачу, на этот раз на связном списке.

Середина связного списка

Дана голова односвязного списка, верните средний узел связного списка.

Наивный подход:

Поместите каждый узел в массив A по порядку. Тогда средний узел будет просто A[A.length // 2]так как мы можем получить каждый узел по индексу.

var middleNode = function(head) {
    let A = [head];
    while (A[A.length - 1].next != null)
        A.push(A[A.length - 1].next);
    return A[Math.trunc(A.length / 2)];
};

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

Подход с двумя указателями:

При обходе списка с указателем slow, сделайте другой указатель fast, который обходит список в два раза быстрее. Когда быстрый достигает конца списка, медленный должен быть в середине.

var middleNode = function(head) {

    let slow = head; 
    let fast = head; 

    while( fast && fast.next){
        slow = slow.next; 
        fast = fast.next.next;
    }

    return slow;
};

• Инициализация: Два указателя стартуют с одной и той же позиции — начала связанного списка.

• Движение: они будут двигаться в одном направлении, но второй быстрее первого.

• Условие остановки: обход остановится, когда указатель, который движется быстрее, достигнет конца связанного списка. Так как более быстрый указатель движется в два раза быстрее медленного, то когда он достигнет конца, медленный окажется в середине.

Временная сложность этого решения составляет O(N), но пространственная сложность составляет только O(1), мы используем дополнительное пространство из-за подхода с двумя указателями. Для этой задачи двухпунктовый подход помогает нам уменьшить пространственную сложность, мы имеем постоянную сложность вместо линейной.

Заключение

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

Надеюсь, это помогло и побудило вас попробовать эту технику, если вы еще этого не сделали.

Ничто 🔺