Skip to content

Sliding Window & Two Pointers 精通地圖 🎯

核心目標：用最常考的「滑動視窗 + 雙指針」題型，建立一套可重用的解題心智模型。
適用：面試準備（NeetCode 150 / Blind 75）、競賽、系統化學演算法。

1️⃣ API Kernel 核心機制

SubstringSlidingWindow（滑動視窗）

  • 定義：在序列上維護動態區間 [left, right]，同時維持某個**不變條件（invariant）**
  • 通用模板（變長視窗）：
left = 0
state = init_state()
ans = init_answer()

for right, x in enumerate(seq):
    add(state, x)          # 擴張右邊

    while violate(state):  # 若不變條件被破壞 → 收縮左邊
        remove(state, seq[left])
        left += 1

    ans = update(ans, left, right, state)  # 視題目而定：取最長/最短/記錄位置

return ans
  • 關鍵思維：
  • 「不變條件」是整個解法的靈魂
  • 視窗只會線性擴張＋收縮 → 時間複雜度多半是 \(O(n)\)

TwoPointersTraversal（雙指針遍歷）

  • 定義：在序列上使用兩個指標，按照某種規則移動，維持一個**關係不變式**
  • 典型子模式：
  • 對向指針：left → ... ← right
  • 同向讀寫指針：read →、write →
  • 通用模板（對向）：
left, right = 0, len(arr) - 1
ans = init_answer()

while left < right:
    cur = evaluate(arr, left, right)
    ans = update(ans, cur, left, right)

    if should_move_left(cur):
        left += 1
    else:
        right -= 1

return ans

FastSlowPointers（快慢指針）

  • 定義：兩個指標在「隱式序列」上以不同速度前進（常見：慢 1 步、快 2 步）
  • 典型用途：
  • 判斷是否有環
  • 找環的起點
  • 找鏈表中點

TwoPointerPartition（雙指針分區）

  • 定義：利用 2～3 個指標在陣列中做原地分區（partition）
  • 常見場景：
  • 荷蘭國旗（0/½ 顏色）
  • 奇偶分區、按條件分組
  • Quickselect / 快速選擇

MergeSortedSequences（合併排序序列）

  • 定義：用雙指針從兩個已排序序列頭或尾開始比較，線性合併
  • 常見場景：
  • 合併兩條已排序鏈表 / 陣列
  • 從兩端「合併平方值」等

2️⃣ Pattern 圖譜：滑動視窗 Sliding Window

2.1 視窗內元素需「全部唯一」：sliding_window_unique 🔑

  • 不變式：視窗內所有字元皆不重複
  • 經典題：
  • LeetCode 3 - Longest Substring Without Repeating Characters（NeetCode 150 / Blind 75 / Grind 75 / Top 100）
  • 重點：
  • last_seen[char] 紀錄**最後一次出現位置**
  • 當遇到重複字元且在視窗內 → left = max(left, last_seen[char] + 1)
  • 這題是所有滑動視窗的「母題」

2.2 視窗中「至多 K 種不同字元」：sliding_window_at_most_k_distinct

2.3 視窗需「涵蓋所有需求頻率」：sliding_window_freq_cover（字頻覆蓋）

  • 不變式：對每個 c，have[c] >= need[c]
  • 子類型：
  • ✅ 最小視窗（變長、求最短）
  • ✅ 固定長度全排列 / anagram 檢查

2.3.1 最小視窗覆蓋：Minimum Window Substring

  • 經典題：
  • LeetCode 76 - Minimum Window Substring（Hard / NeetCode 150 / Blind 75）
  • 模式：
  • 擴張右指針直到「全部需求滿足」
  • 之後盡可能收縮左指針，維持仍然有效 → 取最短長度
  • 心法：
  • need map + have map
  • satisfied_count == required_count 時代表視窗有效

2.3.2 固定長度 anagram / permutation 視窗

2.4 視窗「數值和受限」：sliding_window_cost_bounded

  • 不變式：window_sum >= target（或 <= target 之類）
  • 經典題：
  • LeetCode 209 - Minimum Size Subarray Sum（NeetCode 150 / Sliding Window Path）
  • 關鍵條件：
  • 陣列元素為**正整數** → 和隨視窗擴張單調增加 → 可用雙指針線性掃描
  • 模式：
  • 擴張右邊累加 sum
  • 當 sum >= target → 儘量收縮左邊以縮短長度

2.5 Pattern 對照表 📋

類型 代表題目 不變式 視窗長度 目標
唯一字元 LeetCode 3 視窗內無重複 變長 最大長度
至多 K 種 LeetCode 340 種類數 ≤ K 變長 最大長度
覆蓋所有字頻 LeetCode 76 have ≥ need 變長 最短長度
固定長 anagram LeetCode 567, LeetCode 438 have == need 固定 存在 / 收集所有位置
和 ≥ target LeetCode 209 sum ≥ target 變長 最短長度

3️⃣ Pattern 圖譜：Two Pointers 雙指針

3.1 對向指針：two_pointer_opposite*（Two-End）🔥

適用：排序陣列、對稱結構（回文）、最大化/最小化某函數

3.1.1 兩端收縮最大化函數：two_pointer_opposite_maximize

  • 經典題：
  • LeetCode 11 - Container With Most Water（NeetCode 150 / Blind 75 / Top 100）
  • 思維：
  • 面積 = min(h[left], h[right]) * (right-left)
  • 總是移動**較矮**的那一邊，因為寬度變窄，只有提高短板才可能增大面積

3.1.2 排序後找 pair / 3Sum：two_pointer_opposite_search / two_pointer_three_sum

3.1.3 回文檢查：two_pointer_opposite_palindrome

3.2 同向讀寫指針：two_pointer_writer_*（In-place Writer Pattern）

適用：原地修改陣列，如刪除元素、去重、壓縮

  • 不變式：nums[0:write] 是目前為止的「有效區間」

3.2.1 去重（保留一次 / 保留至多兩次）

3.2.2 移除指定元素 / 壓縮非零：two_pointer_writer_remove / two_pointer_writer_compact

3.3 快慢指針：fast_slow_*（Floyd Cycle / Midpoint）

3.3.1 鏈表是否有環：fast_slow_cycle_detect

  • 經典題：
  • LeetCode 141 - Linked List Cycle
  • 模式：
  • slow = slow.next，fast = fast.next.next
  • 若存在環 → 一定會在環內某點相遇
  • 若 fast 或 fast.next 為 None → 無環

3.3.2 找環起點：fast_slow_cycle_start

  • 經典題：
  • LeetCode 142 - Linked List Cycle II
  • 模式：
  • 第一次相遇後，令一指針從 head 出發，另一留在相遇點
  • 兩者一次一步前進，再次相遇點即為環起點

3.3.3 找中點 / 隱式環：fast_slow_midpoint / fast_slow_implicit_cycle

3.4 Partition / 荷蘭國旗：dutch_flag_partition & two_way_partition

3.5 Merge 模式：merge_two_sorted_* / merge_sorted_from_ends

4️⃣ Data Structure & Algorithm 關聯視角

4.1 常用資料結構 🔧

  • array / string
  • 幾乎所有 sliding window / two pointers 題的基礎
  • hash_map / counter
  • 字頻統計（LeetCode 3, 76, 340, 438, 567）
  • linked_list
  • 快慢指針（LeetCode 141, 142, 876）
  • 原地反轉（LinkedListInPlaceReversal：如 LeetCode 25 - Reverse Nodes in k-Group）
  • queue / grid
  • BFS 多源擴散（LeetCode 994 - Rotting Oranges）

4.2 演算法 / Paradigm 📚

  • Two Pointers / Sliding Window：技術型技巧，常與排序 / hash 搭配
  • Greedy：
  • 容器裝水（LeetCode 11）本質是貪心 + 對向指針
  • Divide & Conquer / Binary Search on Answer：
  • LeetCode 4、LeetCode 215 與 partition 結合
  • Backtracking：
  • 不是雙指針，但在本圖譜中是對比參考（如 LeetCode 51 - N-Queens）

5️⃣ Roadmap：學習路徑建議 🔥

5.1 Sliding Window Mastery Path（對應 sliding_window_path）

5.2 Two Pointers Mastery Path（對應 two_pointers_path）

6️⃣ 面試實戰視角：如何在考場快速判斷用哪個 Pattern？ ⚡

6.1 決策流程（Sliding Window）

答案是否是「連續子陣列 / 子字串」？
├─ 否 → 先考慮 DP / 組合 / 回溯
└─ 是 → 視窗屬性是？
        ├─ 長度固定？→ 固定長滑動視窗（如 567, 438）
        └─ 長度可變：
             ├─ 想「最長」？→ 視窗擴張，違規才收縮（3, 340）
             └─ 想「最短」？→ 先擴張到合法，再極限收縮（76, 209）

6.2 決策流程（Two Pointers）

資料是否已排序（或可以排序）？
├─ 是：
│   ├─ 找 pair / k-sum → 對向指針（11, 15, 16）
│   ├─ 原地刪除/去重 → 同向讀寫（26, 27, 80, 283）
│   ├─ 分區 / 荷蘭國旗 → Partition（75, 905, 922, 215）
│   └─ 合併兩序列 → Merge（21, 88, 977）
└─ 否：
    ├─ 是鏈表？→ 快慢指針（141, 142, 876）
    └─ 其他 → 考慮 hash / heap / BFS / DP 等

7️⃣ 題目難度 & 面試熱門度標記

8️⃣ 實作模板速查（Python）

8.1 滑動視窗：最大化視窗長度

def maximize_window(seq):
    left = 0
    state = {}
    best = 0

    for right, x in enumerate(seq):
        add(state, x)
        while not is_valid(state):  # 視題目定義
            remove(state, seq[left])
            left += 1
        best = max(best, right - left + 1)

    return best

8.2 滑動視窗：最小化視窗長度

def minimize_window(seq):
    left = 0
    state = {}
    best = float("inf")

    for right, x in enumerate(seq):
        add(state, x)
        while is_valid(state):
            best = min(best, right - left + 1)
            remove(state, seq[left])
            left += 1

    return best if best != float("inf") else 0

8.3 對向指針

def two_end(arr):
    left, right = 0, len(arr) - 1
    ans = init_answer()

    while left < right:
        cur = evaluate(arr, left, right)
        ans = update(ans, cur, left, right)

        if move_left(cur):
            left += 1
        else:
            right -= 1

    return ans

8.4 讀寫指針（原地修改）

def reader_writer(nums, keep):
    write = 0
    for read in range(len(nums)):
        if keep(nums, read, write):
            nums[write] = nums[read]
            write += 1
    return write

建議使用方式：
1. 先沿著 Roadmap 把勾選框題目刷一輪
2. 每做完一題，回到本圖譜對照「所屬 Pattern + API Kernel」
3. 嘗試用統一模板重寫一次 → 形成可遷移的解題套路