Algorithme à deux pointeurs expliqué

I want to explain a simple and effective technique that you can use in an interview when dealing with Arrays, Strings, Linked Lists, etc. This will also improve your fundamental knowledge about these data structures.

Let’s start from theory. There are two common use cases of this algorithm:

• left/right The central concept of this algorithm is to have two integer variables that will move from both sides of a string or array. Usually, people call it left and right. The left will move from the 0 index to the length — 1, and the right is the opposite.

• slow/fast Pointers run in the same direction, e.g., from start to end, but one pointer runs faster than another. In this case, people usually call variables slow and fast.

Algorithms are elementary, and the best way to understand them is to look into some examples.

First, let’s look at a case with left and right pointers. Here is an elementary example of a problem we can solve using this algorithm. The goal is clear: we want to find a pair whose sum will equal a given number.
The brute force approach will create nested loops, but there’s a low chance of passing the interview using it.
A better approach would be to use the two pointers algorithm and find it in one loop to have O(n) complexity instead of O(n²)

const findPair = (arr, target) => {
    let left = 0;                 // Start with two pointers left from start, right, from the end
    let right = arr.length - 1;

    while (left < right) { // when pointers meet, finish loop
        const sum = arr[left] + arr[right];

        if (sum === target) {
            return [arr[left], arr[right]];  // Return the pair if we find the target sum
        } else if (sum < target) {
            left++;  // Move left pointer to the right if sum is less than target
        } else {
            right--;  // Move right pointer to the left if sum is greater than target
        }
    }

    return null;  // Return null if no such pair exists
}

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

findPair(arr, target);  // Output: [2, 4]

Let’s switch to an approach where pointers have different speeds. It’s a frequent problem which you can meet an interview. You need to find the middle of the given Linked List.
The brute force approach is not as bad as the previous example, but the interviewer expects a better one.
With two pointers algorithm, you will solve this problem with O(n) complexity, whereas the brute force approach will take O(2n) if you use two sequential loops.

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;           // Move slow pointer one step
        fast = fast.next.next;      // Move fast pointer two steps
    }

    return slow;  // Slow pointer will be at the middle
}

// Creating a linked list 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);  // Output: 3 (middle node)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!