LC算法技巧總結（二）：雙指針和滑動窗口技巧

我把雙指針技巧再分為兩類，一類是「快慢指針」，一類是「左右指針」。前者解決主要解決鏈表中的問題，比如典型的判定鏈表中是否包含環；後者主要解決數組（或者字符串）中的問題，比如二分查找。

一、快慢指針的常見算法

快慢指針一般都初始化指向鏈表的頭結點 head，前進時快指針 fast 在前，慢指針 slow 在後，巧妙解決一些鏈表中的問題。

1、判定鏈表中是否含有環

這應該屬於鏈表最基本的操作了，如果讀者已經知道這個技巧，可以跳過。

單鏈表的特點是每個節點只知道下一個節點，所以一個指針的話無法判斷鏈表中是否含有環的。

如果鏈表中不含環，那麼這個指針最終會遇到空指針 null 表示鏈表到頭了，這還好說，可以判斷該鏈表不含環。

boolean hasCycle(ListNode head) {
    while (head != null)
        head = head.next;
    return false;
}

但是如果鏈表中含有環，那麼這個指針就會陷入死循環，因為環形數組中沒有 null 指針作為尾部節點。

經典解法就是用兩個指針，一個跑得快，一個跑得慢。如果不含有環，跑得快的那個指針最終會遇到 null，說明鏈表不含環；如果含有環，快指針最終會超慢指針一圈，和慢指針相遇，說明鏈表含有環。

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) return true;
    }
    return false;
}

2、已知鏈表中含有環，返回這個環的起始位置

img

這個問題一點都不困難，有點類似腦筋急轉彎，先直接看代碼：

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代碼類似 hasCycle 函數
    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

可以看到，當快慢指針相遇時，讓其中任一個指針指向頭節點，然後讓它倆以相同速度前進，再次相遇時所在的節點位置就是環開始的位置。這是為什麼呢？

第一次相遇時，假設慢指針 slow 走了 k 步，那麼快指針 fast 一定走了 2k 步，也就是說比 slow 多走了 k 步（也就是環的長度）。

img

設相遇點距環的起點的距離為 m，那麼環的起點距頭結點 head 的距離為 k – m，也就是說如果從 head 前進 k – m 步就能到達環起點。

巧的是，如果從相遇點繼續前進 k – m 步，也恰好到達環起點。

img

所以，只要我們把快慢指針中的任一個重新指向 head，然後兩個指針同速前進，k – m 步後就會相遇，相遇之處就是環的起點了。

3、尋找鏈表的中點

類似上面的思路，我們還可以讓快指針一次前進兩步，慢指針一次前進一步，當快指針到達鏈表盡頭時，慢指針就處於鏈表的中間位置。

while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
// slow 就在中間位置
return slow;

當鏈表的長度是奇數時，slow 恰巧停在中點位置；如果長度是偶數，slow 最終的位置是中間偏右：

img

尋找鏈表中點的一個重要作用是對鏈表進行歸併排序。

回想數組的歸併排序：求中點索引遞歸地把數組二分，最後合併兩個有序數組。對於鏈表，合併兩個有序鏈表是很簡單的，難點就在於二分。

但是現在你學會了找到鏈表的中點，就能實現鏈表的二分了。關於歸併排序的具體內容本文就不具體展開了。

4、尋找鏈表的倒數第 k 個元素

我們的思路還是使用快慢指針，讓快指針先走 k 步，然後快慢指針開始同速前進。這樣當快指針走到鏈表末尾 null 時，慢指針所在的位置就是倒數第 k 個鏈表節點（為了簡化，假設 k 不會超過鏈表長度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

二、左右指針的常用算法

左右指針在數組中實際是指兩個索引值，一般初始化為 left = 0, right = nums.length – 1 。

1、二分查找

以前寫的《二分查找》有詳細講解，這裡只寫最簡單的二分算法，旨在突出它的雙指針特性：

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

2、兩數之和

直接看一道 LeetCode 題目（經典Two Sum）吧：

img

只要數組有序，就應該想到雙指針技巧。這道題的解法有點類似二分查找，通過調節 left 和 right 可以調整 sum 的大小：

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 題目要求的索引是從 1 開始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++; // 讓 sum 大一點
        } else if (sum > target) {
            right--; // 讓 sum 小一點
        }
    }
    return new int[]{-1, -1};
}

3、反轉數組

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];Java
        nums[right] = temp;
        left++; right--;
    }
}

4、滑動窗口算法

這也許是雙指針技巧的最高境界了，如果掌握了此算法，可以解決一大類子字符串匹配的問題，不過「滑動窗口」稍微比上述的這些算法複雜些。

詳情見下文（來自東哥的算法講解的思路）

三、滑動窗口技巧

滑動窗口算法框架中，這裡轉自一首小詩來介紹。

本文就解決一類最難掌握的雙指針技巧：滑動窗口技巧。總結出一套框架，可以保你閉着眼睛都能寫出正確的解法。

說起滑動窗口算法，很多讀者都會頭疼。這個算法技巧的思路非常簡單，就是維護一個窗口，不斷滑動，然後更新答案么。LeetCode 上有起碼 10 道運用滑動窗口算法的題目，難度都是中等和困難。該算法的大致邏輯如下：

int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 縮小窗口
        window.remove(s[left]);
        left++;
    }
}

這個算法技巧的時間複雜度是 O(N)，比字符串暴力算法要高效得多。

其實困擾大家的，不是算法的思路，而是各種細節問題。比如說如何向窗口中添加新元素，如何縮小窗口，在窗口滑動的哪個階段更新結果。即便你明白了這些細節，也容易出 bug，找 bug 還不知道怎麼找，真的挺讓人心煩的。

所以今天我就寫一套滑動窗口算法的代碼框架，我連再哪裡做輸出 debug 都給你寫好了，以後遇到相關的問題，你就默寫出來如下框架然後改三個地方就行，還不會出 bug：

/* 滑動窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是將移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 進行窗口內數據的一系列更新
        ...

        /*** debug 輸出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判斷左側窗口是否要收縮
        while (window needs shrink) {
            // d 是將移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 進行窗口內數據的一系列更新
            ...
        }
    }
}

其中兩處 ... 表示的更新窗口數據的地方，到時候你直接往裏面填就行了。

而且，這兩個 ... 處的操作分別是右移和左移窗口更新操作，等會你會發現它們操作是完全對稱的。

說句題外話，我發現很多人喜歡執着於表象，不喜歡探求問題的本質。比如說有很多人評論我這個框架，說什麼散列錶速度慢，不如用數組代替散列表；還有很多人喜歡把代碼寫得特別短小，說我這樣代碼太多餘，影響編譯速度，LeetCode 上速度不夠快。

我服了。算法看的是時間複雜度，你能確保自己的時間複雜度最優，就行了。至於 LeetCode 所謂的運行速度，那個都是玄學，只要不是慢的離譜就沒啥問題，根本不值得你從編譯層面優化，不要捨本逐末……

Tags:

VirMach 便宜 VPS

QNews

QNews