2 ポインター アルゴリズムの説明

面接で配列、文字列、リンク リストなどを扱うときに使用できる、シンプルで効果的なテクニックを説明したいと思います。これにより、これらのデータに関する基本的な知識も向上します。構造。

理論から始めましょう。このアルゴリズムには 2 つの一般的な使用例があります:

• left/right このアルゴリズムの中心的な概念は、文字列または配列の両側から移動する 2 つの整数変数を持つことです。通常、人々はそれを左と右と呼びます。左側はインデックス 0 から長さ — 1 に移動し、右側はその逆です。

• 遅い/速い ポインタは同じ方向に、たとえば最初から最後まで実行されますが、あるポインタは別のポインタよりも速く実行されます。この場合、人々は通常、変数をゆっくりと速く呼び出します。

アルゴリズムは初歩的なものであり、アルゴリズムを理解する最良の方法は、いくつかの例を調べることです。

まず、左右のポインターがある場合を見てみましょう。このアルゴリズムを使用して解決できる問題の基本的な例を次に示します。目標は明らかです。合計が指定された数値に等しくなるペアを見つけたいです。
ブルートフォースアプローチではネストされたループが作成されますが、それを使用して面接に合格する可能性は低いです。
より良いアプローチは、2 ポインター アルゴリズムを使用し、O(n²)

ではなく O(n) の複雑度を持つアルゴリズムを 1 つのループで見つけることです。

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]

ポインタの速度が異なるアプローチに切り替えてみましょう。面接でよくある問題です。指定されたリンク リストの中央を見つける必要があります。
強引なアプローチは前の例ほど悪くはありませんが、面接官はより良いアプローチを期待しています。
2 ポインター アルゴリズムを使用すると、O(n) の複雑さでこの問題を解決できますが、2 つの連続ループを使用する場合、ブルート フォース アプローチでは 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;           // 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)

以上が2 ポインター アルゴリズムの説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。