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

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

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

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

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

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

ポインタの速度が異なるアプローチに切り替えてみましょう。面接でよくある問題です。指定されたリンク リストの中央を見つける必要があります。

ブルートフォースアプローチは前の例ほど悪くはありませんが、面接官はより良いアプローチを期待しています。

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)