引言

雙指針（Two Pointers）是一種非常經典的算法技巧，主要用于數組或鏈表的處理。通過使用兩個指針在序列中移動，可以有效提高算法的效率，通常用于解決涉及子數組、子序列、滑動窗口等問題。

雙指針技巧主要分為：左右指針和快慢指針。

本期文章主要介紹使用快慢指針來解決常見三類問題。

快慢指針

快慢指針：顧名思義，一個指針（快指針）移動速度快，另一個指針（慢指針）移動速度慢。

通常用于解決的問題有：

• 有序數組的原地修改
• 滑動窗口
• 鏈表是否有環

1.數組的原地修改

力扣原題

刪除有序數組中的重復項。

給你一個 非嚴格遞增排列 的數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數。
考慮 nums 的唯一元素的數量為 k ，你需要做以下事情確保你的題解可以被通過：

• 更改數組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。nums 的其余元素與 nums 的大小不重要。
• 返回 k 。

示例 1：
輸入：nums = [1,1,2]
輸出：2, nums = [1,2,_]
解釋：函數應該返回新的長度 2 ，并且原數組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數組中超出新長度后面的元素。

示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5 ， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數組中超出新長度后面的元素。

解題思路

原地修改就是不允許創建一個新數組，必須在原數組上進行操作。

采用雙指針的方法來解決此問題：

• 慢指針（slow）：用于標記處理后數組中唯一元素的位置，初始化為 0。隨著遍歷的進行，慢指針所指向的位置及之前的元素將構成最終的無重復元素序列。
• 快指針（fast）：用于遍歷數組，從 1 開始，依次檢查數組中的每個元素。

在遍歷過程中，對比快指針所指元素和慢指針所指元素：

• 若快指針fast所指元素與慢指針slow所指元素不相等，意味著找到了一個新的唯一元素。此時，將慢指針slow向后移動一位，并把快指針fast所指的這個新的唯一元素賦值到慢指針所指的位置，以此確保唯一元素依次排列在數組的前面部分。
• 若快指針fast所指元素與慢指針slow所指元素相等，表明遇到了重復元素，此時無需對慢指針slow進行操作，直接繼續移動快指針fast去檢查下一個元素。

當快指針fast遍歷完整個數組后，慢指針slow所指向的位置加 1 就是數組中唯一元素的個數 k，而數組的前 k 個元素就是滿足要求的無重復元素序列。

代碼實現

function removeDuplicates(nums: number[]): number {
  if(nums.length === 0) return 0;
  let fast = 0, slow = 0;
  while(fast < nums.length){
    if(nums[fast] !== nums[slow]){
      slow++;
      // 維護 nums[0..slow] 無重復
      nums[slow] = nums[fast];
    }
    fast++;
  }
  // 數組長度為索引 + 1
  return slow + 1;
}

在上述代碼中：

• 首先判斷數組是否為空，如果為空則返回 0。
• 接著通過 for 循環使用雙指針 slow 和 fast 按照既定思路遍歷數組。在循環內，根據快指針和慢指針所指元素是否相等來決定是否移動慢指針以及更新數組元素。
• 最后返回 slow + 1 作為數組中唯一元素的個數，輸出了相應的結果。

這樣就實現了在原數組上刪除重復元素，使每個元素只出現一次，并返回唯一元素個數的功能，同時滿足題目對于數組前 k 個元素的排列要求。

2.滑動窗口

在滑動窗口算法中，雖然不像傳統快慢指針那樣一個指針固定比另一個指針移動速度快，但這里的左右指針（可以類比快慢指針的概念，右指針相對更主動地去擴展窗口，類似快指針的作用；左指針則根據條件收縮窗口，相對慢一些）協同工作來實現窗口的滑動和對數據的處理，以達到我們尋找特定子串或子序列的目的。

力扣原題

最小覆蓋子串。

給你一個字符串 s 和一個字符串 t，請你找出 s 中包含 t 所有字符的最小子串。如果不存在這樣的子串，就返回空字符串 ""。
示例 1：
輸入：s = "ADOBECODEBANC", t = "ABC"
解釋：最小覆蓋子串是 "BANC"，它包含了字符串 "ABC" 中的所有字符。

解題思路

（1）窗口的初始化

使用指針left和指針right來定義一個滑動窗口的左右邊界。使用合適的數據結構保存滑動窗口中的元素，根據實際場景進行設計，具體的：

• 想要記錄窗口中元素出現的次數，可以用 Map。
• 想要記錄窗口中的元素和，可以用 number。

其實也可以使用數組或對象等數據結構。

（2）窗口的移動與條件判斷：

向右擴展窗口，移動right指針，每次將s[right]加入到窗口中，并更新對應元素出現的次數。

判斷窗口是否符合條件，通過變量 valid，用于記錄當前窗口內已經滿足目標字符串 t 中字符需求的字符種類數量。每次更新窗口的元素記錄后，檢查當前窗口的每個元素是否符合條件，達到了valid進行加1操作。

收縮窗口，移動left指針。當找到了一個包含目標字符串所有字符的窗口后，通過移動 left 指針來縮小窗口，以找到最小的覆蓋子串。

在移動 left 指針時，需要更新 windows Map 中對應字符的出現次數，并檢查是否會因為移除了某個字符而導致窗口不再滿足條件（即 valid 的值小于目標字符串 t 中不同字符的種類數量）。

代碼實現

function minWindow(s: string, t: string): string {
    // 如果字符串 s 的長度小于字符串 t 的長度，則不可能找到符合條件的子串，直接返回空字符串
    if (s.length < t.length) return "";

    // 將 t 中的字符存進 need Map 中進行計數
    const need = new Map();
    for (const char of t) {
        need.set(char, (need.get(char) || 0) + 1);
    }

    // 定義一個 Map 來統計滑動窗口中的字符
    const windows = new Map();
    // 滑動窗口的左右指針索引
    let left = 0, right = 0;
    let valid = 0; // 用來存滑動窗口中滿足 need 條件的字符個數（即有效字符數）
    let start = 0; // 保存符合條件的最小子串的起始索引
    let len = Number.MAX_SAFE_INTEGER; // 當前最小子串的長度

    // 開始滑動窗口
    while (right < s.length) {
        // 即將進入窗口的字符
        const r = s[right];
        right++; // 擴大窗口
        // 如果 r 是需要的字符，則加入到窗口統計中
        if (need.has(r)) {
            windows.set(r, (windows.get(r) || 0) + 1);
            // 判斷窗口中的這個字符統計數是否已經滿足 need 的要求，如果滿足則有效字符數 valid 加一
            if (windows.get(r) === need.get(r)) {
                valid++;
            }
        }

        // 當窗口中的有效字符個數等于需要的字符個數時，嘗試收縮窗口
        while (valid === need.size) {
            // 更新最小子串的索引和長度
            if (right - left < len) {
                len = right - left;
                start = left;
            }

            // 即將移除窗口的字符
            const l = s[left];
            left++; // 收縮窗口
            // 如果 l 是需要的字符，則更新窗口統計數據
            if (need.has(l)) {
                // 如果當前窗口中的 l 個數剛好等于 need 中的個數，移除后有效字符數 valid 減一
                if (windows.get(l) === need.get(l)) {
                    valid--;
                }
                // 更新窗口中 l 字符的數量
                windows.set(l, windows.get(l) - 1);
            }
        }
    }

    // 如果 len 還是初始值，說明沒有符合條件的子串，返回 ""
    return len === Number.MAX_SAFE_INTEGER ? "" : s.slice(start, start + len);
}

3.鏈表是否有環

在處理鏈表數據結構時，判斷鏈表是否存在環是一個常見的問題。所謂環，就是鏈表中的某個節點可以通過連續跟蹤 next 指針再次回到之前已經訪問過的節點，形成一個類似環形的結構。

使用快慢指針算法可以高效地解決這個問題，通過讓兩個指針以不同的速度在鏈表上移動，根據它們是否相遇來判斷鏈表是否存在環。

力扣原題

環形鏈表。

給你一個鏈表的頭節點 head ，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤 next 指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。

注意：pos 不作為參數進行傳遞 。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環 ，則返回 true 。 否則，返回 false 。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

解題思路

指針的定義與初始化：

• 我們定義兩個指針，分別為慢指針（slow）和快指針（slow）。
• 這兩個指針都初始化為鏈表的頭節點（head），即 slow = head，fast = head。

指針的移動規則：

• 慢指針（slow）每次移動一步，也就是 slow = slow.next。
• 快指針（fast）每次移動兩步，即 fast = fast.next.next。這里要特別留意，在移動快指針時，必須先確保 fast 和 fast.next 不為空，不然會出現空指針訪問的錯誤。

判斷是否有環的依據：

• 當鏈表中存在環時，由于快指針的移動速度是慢指針的兩倍，所以快指針會在環內逐漸追上慢指針。具體而言，在持續移動指針的過程中，最終將會出現 slow === fast 的情形，此時便可判定鏈表存在環。
• 倘若在移動指針的過程中，快指針碰到了鏈表的末尾（也就是 fast === null 或者 fast.next === null），這就表明鏈表中不存在環，因為快指針已經遍歷完整個鏈表且未進入環中。

代碼實現

// 判斷鏈表是否有環的函數
function hasCycle(head: ListNode | null): boolean {
    // 如果鏈表頭節點為空，說明鏈表為空鏈表，自然不存在環，直接返回false
    if (head === null) {
        return false;
    }

    // 初始化慢指針slow，使其指向鏈表的頭節點head
    let slow: ListNode | null = head;
    // 初始化快指針fast，同樣使其指向鏈表的頭節點head
    let fast: ListNode | null = head;

    // 進入循環，只要快指針fast不為空且快指針的下一個節點fast.next也不為空，就繼續循環
    // 因為快指針每次移動兩步，所以需要確保它和它的下一個節點都存在，否則會出現空指針訪問的錯誤
    while (fast!== null && fast.next!== null) {
        // 慢指針每次移動一步，將慢指針指向它當前所指節點的下一個節點
        slow = slow!.next;
        // 快指針每次移動兩步，先將快指針指向它當前所指節點的下一個節點的下一個節點
        fast = fast!.next.next;

        // 在每次移動指針后，檢查慢指針和快指針是否指向了同一個節點
        // 如果是，說明快指針在環內追上了慢指針，也就意味著鏈表存在環，此時返回true
        if (slow === fast) {
            return true;
        }
    }

    // 如果循環結束后，沒有出現慢指針和快指針指向同一個節點的情況，
    // 那就說明快指針已經遍歷完整個鏈表且未進入環中，即鏈表不存在環，返回false
    return false;
}

總結

雙指針技巧中的快慢指針在算法問題解決中意義重大。

• 對于有序數組原地修改，可高效去重；
• 滑動窗口能借助其找到最小覆蓋子串；
• 鏈表中可判斷是否有環。

它通過巧妙的指針移動規則和條件判斷，有效提高處理數組和鏈表相關問題的效率。