跳至主要内容

雙指標與滑動視窗（Two Pointers / Sliding Window）

雙指標與滑動視窗是同一個核心思想的不同面貌：與其用兩層迴圈把所有配對都掃一遍（O(n²)），不如用兩個索引在陣列／字串上移動，讓每個元素只被看常數次，把問題壓到 O(n)。它們是陣列與字串題最主力的手法，面試出現率極高——認得出模式，題目就從「想不到」變「照套」。

一、對撞指標：一頭一尾往中間夾​

兩個指標分別從兩端往中間走，適合有序陣列，或需要「同時看頭尾」的題。

有序陣列 two-sum（LeetCode 167）：找兩個數和為 target。左右指標指頭尾，看當前和：太小就左指標右移（換大一點的數）、太大就右指標左移。因為陣列有序，每次移動都排除掉一整排不可能的配對，一趟就掃完。

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1          # 和太小，只能把小的那端換大
        else:
            hi -= 1          # 和太大，把大的那端換小
    return []

判回文（LeetCode 125）：左右指標往中間比對，一遇不同就 return False。

三數之和（LeetCode 15）：先排序，固定第一個數，剩下兩個數就退化成「有序 two-sum」用對撞指標——把 O(n³) 的暴力降到 O(n²)。難點在去重（跳過相同值），是面試常見的扣分點。

對撞指標能成立的前提通常是有序：有序才讓「往哪邊移」有明確的單調意義。看到「排序後」或「已排序陣列」＋「找配對／區間」，先想對撞指標。

二、快慢指標：一個跑得比另一個快​

兩個指標同向移動但速度不同，適合鏈結串列與原地改陣列。

環偵測（Floyd 龜兔賽跑）（LeetCode 141）：慢指標一次一步、快指標一次兩步。有環的話快指標終究會從後面追上慢指標（兩者相遇）；無環則快指標先到終點。O(1) 空間判環，是快慢指標的招牌。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # 一次一步
        fast = fast.next.next       # 一次兩步
        if slow is fast:            # 相遇 → 有環
            return True
    return False

找中點：快指標到底時，慢指標剛好在中間（呼應 Single Linked List 的 fast-slow 找中點）。原地去重（LeetCode 26）：慢指標標記「已整理好的邊界」，快指標往前掃、遇到新值才寫回慢指標位置——一個陣列同時當輸入和輸出。

三、滑動視窗：維護一段連續區間​

滑動視窗是雙指標用在連續子陣列／子字串的特例：left／right 圍出一個視窗，right 不斷往右擴張納入新元素，一旦視窗違反條件就收縮 left。每個元素最多被 right 納入一次、被 left 移出一次，所以總工作量是 O(n)。

固定大小視窗：窗長固定為 k，右進一個、左出一個，維護窗內的和／計數（如長度 k 的最大子陣列和）。

可變大小視窗是更常見也更難的一類。經典題最長不重複子字串（LeetCode 3）：視窗內不能有重複字元，用一個集合／字典記錄窗內字元，right 遇到重複就一直收縮 left 直到重複消失。

def length_of_longest_substring(s):
    seen = {}                       # 字元 -> 最後出現的 index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # 跳過上一個重複位置，收縮左界
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

最小覆蓋子字串（LeetCode 76）是可變視窗的天花板題：找 s 中最短、涵蓋 t 所有字元的子字串。用一個 need 計數表，right 擴張到「窗內湊齊 t」後，再拚命收縮 left 找最短的合法窗，過程記錄最小值。判斷「湊齊了沒」用一個 formed 計數避免每次重掃整張表，是把它做到 O(n) 的關鍵。

四、和單調堆疊的分工​

同樣是線性掃描，單調堆疊 與滑動視窗解的是不同形狀的問題：

手法解什麼維護的東西
滑動視窗一段連續區間的性質（和、長度、字元集合）left／right 兩個邊界
單調堆疊每個元素左右第一個更大／更小的鄰居一個保持單調的 stack
對撞指標有序陣列上的配對／區間一頭一尾兩個指標

三者常常在同一題的不同子步驟出現。例如滑動視窗最大值（LeetCode 239）就是「可變視窗 + 單調佇列（monotonic deque）」的合體——視窗滑動由雙指標控制，窗內最大值由單調結構 O(1) 取得。

五、怎麼認出可以用、與常見陷阱​

辨識訊號：題目出現「連續子陣列／子字串」「最長／最短滿足某條件的區間」「兩數／三數之和」「已排序」「原地（O(1) 空間）」這類字眼，十之八九是雙指標或滑動視窗。

陷阱：

  • 對撞指標要先確認有序。沒排序就用對撞指標會得到錯答案；若題目允許排序，先排序的 O(n log n) 常常仍優於 O(n²) 暴力。
  • 滑動視窗的收縮條件：想清楚「什麼時候該收縮 left」——是 while（收到合法為止）還是 if（收一格）。這是最容易寫錯的地方。
  • 視窗內狀態的增減要對稱：right 納入時做的更新，left 移出時要有對應的反向更新，否則狀態會漂掉。
  • 負數會破壞單調性：滑動視窗依賴「擴張讓量變大、收縮讓量變小」的單調性。若陣列有負數（如「和為 k 的子陣列」），視窗的單調前提不成立，得改用前綴和 + hash map。這是面試官從正數題臨時加負數時的考點。

LeetCode 練習​

題號題目模式
167Two Sum II (Input Sorted)對撞指標
153Sum排序 + 對撞指標 + 去重
125Valid Palindrome對撞指標
141Linked List Cycle快慢指標（Floyd）
26Remove Duplicates from Sorted Array快慢指標原地改寫
3Longest Substring Without Repeating可變滑動視窗
209Minimum Size Subarray Sum可變滑動視窗（正數）
76Minimum Window Substring可變滑動視窗 + 計數表
239Sliding Window Maximum滑動視窗 + 單調佇列