引言

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

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

本期文章主要介紹使用快慢指針來(lái)解決常見三類問(wèn)題。

快慢指針

快慢指針：顧名思義，一個(gè)指針（快指針）移動(dòng)速度快，另一個(gè)指針（慢指針）移動(dòng)速度慢。

通常用于解決的問(wèn)題有：

• 有序數(shù)組的原地修改
• 滑動(dòng)窗口
• 鏈表是否有環(huán)

1.數(shù)組的原地修改

力扣原題

刪除有序數(shù)組中的重復(fù)項(xiàng)。

給你一個(gè) 非嚴(yán)格遞增排列 的數(shù)組 nums ，請(qǐng)你 原地 刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長(zhǎng)度。元素的 相對(duì)順序 應(yīng)該保持 一致 。然后返回 nums 中唯一元素的個(gè)數(shù)。
考慮 nums 的唯一元素的數(shù)量為 k ，你需要做以下事情確保你的題解可以被通過(guò)：

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

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

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

解題思路

原地修改就是不允許創(chuàng)建一個(gè)新數(shù)組，必須在原數(shù)組上進(jìn)行操作。

采用雙指針的方法來(lái)解決此問(wèn)題：

• 慢指針（slow）：用于標(biāo)記處理后數(shù)組中唯一元素的位置，初始化為 0。隨著遍歷的進(jìn)行，慢指針?biāo)赶虻奈恢眉爸暗脑貙?gòu)成最終的無(wú)重復(fù)元素序列。
• 快指針（fast）：用于遍歷數(shù)組，從 1 開始，依次檢查數(shù)組中的每個(gè)元素。

在遍歷過(guò)程中，對(duì)比快指針?biāo)冈睾吐羔標(biāo)冈兀?/p>

• 若快指針fast所指元素與慢指針slow所指元素不相等，意味著找到了一個(gè)新的唯一元素。此時(shí)，將慢指針slow向后移動(dòng)一位，并把快指針fast所指的這個(gè)新的唯一元素賦值到慢指針?biāo)傅奈恢茫源舜_保唯一元素依次排列在數(shù)組的前面部分。
• 若快指針fast所指元素與慢指針slow所指元素相等，表明遇到了重復(fù)元素，此時(shí)無(wú)需對(duì)慢指針slow進(jìn)行操作，直接繼續(xù)移動(dòng)快指針fast去檢查下一個(gè)元素。

當(dāng)快指針fast遍歷完整個(gè)數(shù)組后，慢指針slow所指向的位置加 1 就是數(shù)組中唯一元素的個(gè)數(shù) k，而數(shù)組的前 k 個(gè)元素就是滿足要求的無(wú)重復(fù)元素序列。

代碼實(shí)現(xiàn)

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++;
      // 維護(hù) nums[0..slow] 無(wú)重復(fù)
      nums[slow] = nums[fast];
    }
    fast++;
  }
  // 數(shù)組長(zhǎng)度為索引 + 1
  return slow + 1;
}

在上述代碼中：

• 首先判斷數(shù)組是否為空，如果為空則返回 0。
• 接著通過(guò) for 循環(huán)使用雙指針 slow 和 fast 按照既定思路遍歷數(shù)組。在循環(huán)內(nèi)，根據(jù)快指針和慢指針?biāo)冈厥欠裣嗟葋?lái)決定是否移動(dòng)慢指針以及更新數(shù)組元素。
• 最后返回 slow + 1 作為數(shù)組中唯一元素的個(gè)數(shù)，輸出了相應(yīng)的結(jié)果。

這樣就實(shí)現(xiàn)了在原數(shù)組上刪除重復(fù)元素，使每個(gè)元素只出現(xiàn)一次，并返回唯一元素個(gè)數(shù)的功能，同時(shí)滿足題目對(duì)于數(shù)組前 k 個(gè)元素的排列要求。

2.滑動(dòng)窗口

在滑動(dòng)窗口算法中，雖然不像傳統(tǒng)快慢指針那樣一個(gè)指針固定比另一個(gè)指針移動(dòng)速度快，但這里的左右指針（可以類比快慢指針的概念，右指針相對(duì)更主動(dòng)地去擴(kuò)展窗口，類似快指針的作用；左指針則根據(jù)條件收縮窗口，相對(duì)慢一些）協(xié)同工作來(lái)實(shí)現(xiàn)窗口的滑動(dòng)和對(duì)數(shù)據(jù)的處理，以達(dá)到我們尋找特定子串或子序列的目的。

力扣原題

最小覆蓋子串。

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

解題思路

（1）窗口的初始化

使用指針left和指針right來(lái)定義一個(gè)滑動(dòng)窗口的左右邊界。使用合適的數(shù)據(jù)結(jié)構(gòu)保存滑動(dòng)窗口中的元素，根據(jù)實(shí)際場(chǎng)景進(jìn)行設(shè)計(jì)，具體的：

• 想要記錄窗口中元素出現(xiàn)的次數(shù)，可以用 Map。
• 想要記錄窗口中的元素和，可以用 number。

其實(shí)也可以使用數(shù)組或?qū)ο蟮葦?shù)據(jù)結(jié)構(gòu)。

（2）窗口的移動(dòng)與條件判斷：

向右擴(kuò)展窗口，移動(dòng)right指針，每次將s[right]加入到窗口中，并更新對(duì)應(yīng)元素出現(xiàn)的次數(shù)。

判斷窗口是否符合條件，通過(guò)變量 valid，用于記錄當(dāng)前窗口內(nèi)已經(jīng)滿足目標(biāo)字符串 t 中字符需求的字符種類數(shù)量。每次更新窗口的元素記錄后，檢查當(dāng)前窗口的每個(gè)元素是否符合條件，達(dá)到了valid進(jìn)行加1操作。

收縮窗口，移動(dòng)left指針。當(dāng)找到了一個(gè)包含目標(biāo)字符串所有字符的窗口后，通過(guò)移動(dòng) left 指針來(lái)縮小窗口，以找到最小的覆蓋子串。

在移動(dòng) left 指針時(shí)，需要更新 windows Map 中對(duì)應(yīng)字符的出現(xiàn)次數(shù)，并檢查是否會(huì)因?yàn)橐瞥四硞€(gè)字符而導(dǎo)致窗口不再滿足條件（即 valid 的值小于目標(biāo)字符串 t 中不同字符的種類數(shù)量）。

代碼實(shí)現(xiàn)

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

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

    // 定義一個(gè) Map 來(lái)統(tǒng)計(jì)滑動(dòng)窗口中的字符
    const windows = new Map();
    // 滑動(dòng)窗口的左右指針?biāo)饕?    let left = 0, right = 0;
    let valid = 0; // 用來(lái)存滑動(dòng)窗口中滿足 need 條件的字符個(gè)數(shù)（即有效字符數(shù)）
    let start = 0; // 保存符合條件的最小子串的起始索引
    let len = Number.MAX_SAFE_INTEGER; // 當(dāng)前最小子串的長(zhǎng)度

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

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

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

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

3.鏈表是否有環(huán)

在處理鏈表數(shù)據(jù)結(jié)構(gòu)時(shí)，判斷鏈表是否存在環(huán)是一個(gè)常見的問(wèn)題。所謂環(huán)，就是鏈表中的某個(gè)節(jié)點(diǎn)可以通過(guò)連續(xù)跟蹤 next 指針再次回到之前已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，形成一個(gè)類似環(huán)形的結(jié)構(gòu)。

使用快慢指針?biāo)惴梢愿咝У亟鉀Q這個(gè)問(wèn)題，通過(guò)讓兩個(gè)指針以不同的速度在鏈表上移動(dòng)，根據(jù)它們是否相遇來(lái)判斷鏈表是否存在環(huán)。

力扣原題

環(huán)形鏈表。

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。

注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

解題思路

指針的定義與初始化：

• 我們定義兩個(gè)指針，分別為慢指針（slow）和快指針（slow）。
• 這兩個(gè)指針都初始化為鏈表的頭節(jié)點(diǎn)（head），即 slow = head，fast = head。

指針的移動(dòng)規(guī)則：

• 慢指針（slow）每次移動(dòng)一步，也就是 slow = slow.next。
• 快指針（fast）每次移動(dòng)兩步，即 fast = fast.next.next。這里要特別留意，在移動(dòng)快指針時(shí)，必須先確保 fast 和 fast.next 不為空，不然會(huì)出現(xiàn)空指針訪問(wèn)的錯(cuò)誤。

判斷是否有環(huán)的依據(jù)：

• 當(dāng)鏈表中存在環(huán)時(shí)，由于快指針的移動(dòng)速度是慢指針的兩倍，所以快指針會(huì)在環(huán)內(nèi)逐漸追上慢指針。具體而言，在持續(xù)移動(dòng)指針的過(guò)程中，最終將會(huì)出現(xiàn) slow === fast 的情形，此時(shí)便可判定鏈表存在環(huán)。
• 倘若在移動(dòng)指針的過(guò)程中，快指針碰到了鏈表的末尾（也就是 fast === null 或者 fast.next === null），這就表明鏈表中不存在環(huán)，因?yàn)榭熘羔樢呀?jīng)遍歷完整個(gè)鏈表且未進(jìn)入環(huán)中。

代碼實(shí)現(xiàn)

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

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

    // 進(jìn)入循環(huán)，只要快指針fast不為空且快指針的下一個(gè)節(jié)點(diǎn)fast.next也不為空，就繼續(xù)循環(huán)
    // 因?yàn)榭熘羔樏看我苿?dòng)兩步，所以需要確保它和它的下一個(gè)節(jié)點(diǎn)都存在，否則會(huì)出現(xiàn)空指針訪問(wèn)的錯(cuò)誤
    while (fast!== null && fast.next!== null) {
        // 慢指針每次移動(dòng)一步，將慢指針指向它當(dāng)前所指節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        slow = slow!.next;
        // 快指針每次移動(dòng)兩步，先將快指針指向它當(dāng)前所指節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        fast = fast!.next.next;

        // 在每次移動(dòng)指針后，檢查慢指針和快指針是否指向了同一個(gè)節(jié)點(diǎn)
        // 如果是，說(shuō)明快指針在環(huán)內(nèi)追上了慢指針，也就意味著鏈表存在環(huán)，此時(shí)返回true
        if (slow === fast) {
            return true;
        }
    }

    // 如果循環(huán)結(jié)束后，沒(méi)有出現(xiàn)慢指針和快指針指向同一個(gè)節(jié)點(diǎn)的情況，
    // 那就說(shuō)明快指針已經(jīng)遍歷完整個(gè)鏈表且未進(jìn)入環(huán)中，即鏈表不存在環(huán)，返回false
    return false;
}

總結(jié)

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

• 對(duì)于有序數(shù)組原地修改，可高效去重；
• 滑動(dòng)窗口能借助其找到最小覆蓋子串；
• 鏈表中可判斷是否有環(huán)。

它通過(guò)巧妙的指針移動(dòng)規(guī)則和條件判斷，有效提高處理數(shù)組和鏈表相關(guān)問(wèn)題的效率。