Пояснення алгоритму Two Pointers | Блог

Я хочу пояснити просту та ефективну техніку, яку ви можете використати на співбесіді під час роботи з масивами, рядками, зв’язними списками тощо. Це також допоможе вам покращити базові знання про ці структури даних. Почнемо з теорії - є два поширені випадки використання цього алгоритму.

left/right

Центральна ідея цього алгоритму полягає в тому, щоб мати дві змінні типу integer, які рухаються з обох боків рядка або масиву. Зазвичай їх називають left і right. left рухається від індексу 0 до length - 1, а right - у протилежному напрямку.

slow/fast

Вказівники рухаються в одному напрямку, наприклад, від початку до кінця, але один рухається швидше за інший. У цьому випадку змінні зазвичай називають slow і fast.

Алгоритми є базовими, і найкращий спосіб зрозуміти їх - це розглянути кілька прикладів. Спочатку розглянемо випадок із вказівниками left і right. Ось простий приклад задачі, яку можна розв’язати за допомогою цього алгоритму. Мета зрозуміла: ми хочемо знайти пару елементів, сума яких дорівнює заданому числу. Підхід brute force передбачає створення вкладених циклів, але з ним невеликі шанси успішно пройти співбесіду.

Кращим рішенням буде використати алгоритм двох вказівників і знайти потрібну пару за один прохід, отримавши складність O(n) замість O(n²).

const findPair = (arr, target) => {

let left = 0; // Починаємо з двох вказівників: left — з початку, right — з кінця

let right = arr.length - 1;

while (left < right) { // Коли вказівники зустрічаються — завершуємо цикл

const sum = arr[left] + arr[right];

if (sum === target) {

return [arr[left], arr[right]]; // Повертаємо пару, якщо знайшли потрібну суму

} else if (sum < target) {

left++; // Рухаємо left вправо, якщо сума менша за target

} else {

right--; // Рухаємо right вліво, якщо сума більша за target

}

return null; // Повертаємо null, якщо такої пари не існує

}

const arr = [1, 2, 3, 4, 6];

const target = 6;

findPair(arr, target); // Результат: [2, 4]

Перейдемо до підходу, де вказівники рухаються з різною швидкістю. Це досить поширена задача, яку можна зустріти на співбесіді. Потрібно знайти середину заданого зв’язного списку (Linked List). Підхід brute force тут не такий поганий, як у попередньому прикладі, але інтерв’юер очікує кращого рішення. Використовуючи алгоритм двох вказівників, ви зможете розв’язати цю задачу зі складністю O(n), тоді як brute force підхід займе O(2n), якщо використовувати два послідовні цикли.

class ListNode {

constructor(value) {

this.value = value;

this.next = null;

}

const findMiddle = (head) => {

if (!head) return null;

let slow = head;

let fast = head;

while (fast && fast.next) {

slow = slow.next; // Рухаємо slow на один крок

fast = fast.next.next; // Рухаємо fast на два кроки

}

return slow; // Вказівник slow буде на середині списку

}

// Створюємо зв’язний список 1 -> 2 -> 3 -> 4 -> 5

const head = new ListNode(1);

const node2 = new ListNode(2);

const node3 = new ListNode(3);

const node4 = new ListNode(4);

const node5 = new ListNode(5);

head.next = node2;

node2.next = node3;

node3.next = node4;

node4.next = node5;

findMiddle(head).value; // Результат: 3 (середня нода)