雙指標與滑動視窗（sliding window）技巧教學

這些技巧解決什麼問題

許多陣列與字串問題都在問成對元素或連續區間：兩個數字相加等於目標值、不含重複字元的最長子字串、總和至少為 k 的最短子陣列。逐一檢查每一對或每一段區間，成本是 O(n²) 甚至更高。雙指標利用資料的某種性質（例如已排序，或視窗只需小幅更新），一次排除許多候選，從而避開這種成本。

兩端指標：已排序陣列中的兩數和

在已排序的串列 [1, 3, 4, 6, 8, 11] 中找出兩個總和為 10 的數。從最小與最大的數開始。若總和太小，唯一能增加它的方法是把 left 往右移；若總和太大，就把 right 往左移。

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

每一步都讓一個指標向內移動，所以最多 n − 1 步：時間 O(n)、空間 O(1)。同樣的做法可用來檢查字串是否為回文、原地反轉陣列，再放進外層迴圈，還能把 3Sum 從 O(n³) 降到 O(n²)。

快慢指標：原地過濾

慢指標標示下一個保留元素該放的位置；快指標掃過每個元素。這樣不需額外記憶體，就能從已排序的串列中移除重複項。

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

在鏈結串列上，快指標每步走兩個節點，慢指標走一個。若兩者相遇，串列就有環（Floyd 環偵測演算法）；當快指標走到尾端時，慢指標恰好在中間。

滑動視窗：不含重複字元的最長子字串

滑動視窗讓範圍 s[left:right + 1] 始終保持有效。每次將 right 往前移一個字元。當新字元違反規則，就把 left 往前移，直到視窗再度有效。過程中記錄最佳視窗。

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

視窗有兩種。固定大小的視窗含 k 個元素，每次加入右邊進來的元素、移除左邊離開的元素，例如用來計算移動平均。可變大小的視窗則會依條件伸縮，如上面的例子。

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

時間與空間複雜度

即使有巢狀的 while 迴圈，滑動視窗仍是 O(n) 的原因：left 與 right 各自整個過程中最多往前移動 n 次，所以總工作量至多 2n 步。

常見錯誤

• 對未排序的資料使用兩端指標。決定要移動左邊或右邊，只有在陣列已排序時才正確。
• 數字可能為負時，仍使用以總和為基礎的滑動視窗。此時縮小視窗不一定會讓總和變小；請改用前綴和搭配雜湊表。
• 視窗長度差一：包含兩端的視窗 left..right 有 right - left + 1 個元素。
• 忘了在 left < right 時停止，會讓單一元素與自己配成一對。
• 讓 left 往回移。在子字串範例中，last_seen[ch] >= left 的檢查可避免跳回舊位置。

何時使用，以及典型面試題

當輸入已排序（或能以低成本排序）而你要找成對元素，或需要原地修改陣列時，就用雙指標。當題目提到連續子陣列或子字串，並要求最長、最短、最大或計數，且條件會隨視窗擴大而可預測地變化時，就用滑動視窗。如果資料未排序又要找成對元素，雜湊集合通常更簡單，同樣是 O(n)。

• Two Sum II（輸入已排序）、3Sum、Container With Most Water、Trapping Rain Water。
• Valid Palindrome、Reverse String、Move Zeroes、Remove Duplicates from Sorted Array。
• Longest Substring Without Repeating Characters、Minimum Window Substring、Sliding Window Maximum（搭配 deque）。
• Linked List Cycle、Middle of the Linked List。

在面試之外，同樣的概念也出現在合併已排序檔案、追蹤未確認封包視窗的網路協定（TCP 滑動視窗）、計算最近 N 秒內事件數的限流器，以及時間序列的移動平均。