」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > 二指針演算法解釋

二指針演算法解釋

發佈於2024-11-08
瀏覽:652

Two pointers algorithm explained

我想解釋一個簡單有效的技巧,你可以在面試中處理數組、字串、鍊錶等時使用它。這也將提高你對這些數據的基礎知識結構。

讓我們從理論開始。該演算法有兩個常見用例:

  • left/right 這個演算法的中心概念是有兩個整數變量,它們將從字串或數組的兩側移動。通常,人們稱之為左和右。左邊將從0索引移動到長度-1,右邊則相反。

  • 慢/快 指標以相同方向運行,例如,從開始到結束,但一個指標比另一個指標運行得更快。在這種情況下,人們通常稱變數為慢速和快速。

演算法是基本的,理解它們的最佳方法是研究一些例子。

首先我們來看一個左右指針的情況。這是我們可以使用該演算法解決的問題的基本範例。目標很明確:我們想要找到一對總和等於給定數字的對。
暴力方法會產生嵌套循環,但使用它通過面試的機會很低。
更好的方法是使用兩個指標演算法並在一個循環中找到它以具有 O(n) 複雜度而不是 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 

讓我們切換到指針有不同速度的方法。這是一個常見的問題,你可以在面試中遇到。您需要找到給定連結清單的中間位置。
蠻力方法不像前面的例子那麼糟糕,但面試官期望有更好的方法。
使用兩個指標演算法,您將以 O(n) 複雜度解決此問題,而如果您使用兩個順序循環,暴力方法將需要 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)


版本聲明 本文轉載於:https://dev.to/okaz/two-pointers-algorithm-explained-3k0e?1如有侵犯,請聯絡[email protected]刪除
最新教學 更多>

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3