我們來詳細講解一下算法中非常常用且重要的技巧——雙指針法。
這是一個概念清晰但應用極其廣泛的技術，掌握它能幫助你高效解決許多問題。
一、什么是雙指針法？
核心思想：顧名思義，就是在遍歷對象（通常是數組或鏈表）時，使用兩個相同方向或相反方向的指針（索引）進行掃描，通過指針的移動和相互配合來解決問題，從而避免不必要的循環，將暴力解法的時間復雜度優化到 O(n) 級別。
為什么有效？ 它通過巧妙地利用問題的內在邏輯（如有序性），避免了大量的重復計算，將復雜度從 O(n2) 降低到 O(n)。
二、雙指針的三種常見類型
雙指針法主要有三種常見的應用形式，我們結合例子來理解。
1. 快慢指針（前后指針）
兩個指針從同一側開始遍歷，但移動速度不同（例如，一個一次走一步，一個一次走兩步）。常用于鏈表問題。
典型問題：判斷鏈表是否有環
? 思路：設置兩個指針 slow 和 fast，起始位置都在鏈表頭。
? slow 每次向后移動一個節點。? fast 每次向后移動兩個節點。
? 判斷：
? 如果鏈表中沒有環，fast 指針會先到達鏈表尾部（遇到 null）。? 如果鏈表中有環，fast 指針最終會追上 slow 指針（fast == slow），就像在環形跑道上賽跑一樣。
? 代碼示例 (Python)
class ListNode:
def init(self, x):
self.val = x
self.next = None
def hasCycle(head: ListNode) -> bool:if not head or not head.next:return Falseslow = headfast = head.nextwhile slow != fast:# 如果fast或fast.next為空，說明到了鏈表末尾，無環if not fast or not fast.next:return Falseslow = slow.nextfast = fast.next.next # fast每次走兩步# 如果slow等于fast，說明有環return True
? 其他應用：尋找鏈表的中間節點、尋找鏈表的倒數第 k 個節點。
2. 左右指針（對撞指針）
兩個指針分別從序列的兩端向中間移動，直到它們相遇。前提通常是序列是有序的。
典型問題：兩數之和 II - 輸入有序數組 (LeetCode 167)
題目：給定一個已按升序排列的整數數組 numbers，請你從數組中找出兩個數滿足相加之和等于目標數 target。假設每個輸入只對應唯一的答案，且不可以重復使用相同的元素。
? 暴力法：兩層循環，時間復雜度 O(n2)。
? 雙指針法：利用有序這個關鍵特性。
? 步驟：1. 初始化：左指針 left = 0，右指針 right = len(numbers) - 1。2. 循環條件：while left < right。3. 計算 sum_val = numbers[left] + numbers[right]。4. 判斷：? 如果 sum_val == target，找到答案，返回 [left+1, right+1] (題目要求索引從1開始)。? 如果 sum_val < target，說明總和太小，需要增大。因為數組有序，所以將 left 右移（left += 1）。? 如果 sum_val > target，說明總和太大，需要減小。將 right 左移（right -= 1）。
? 代碼示例 (Python)
def twoSum(numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:s = numbers[left] + numbers[right]if s == target:return [left + 1, right + 1]elif s < target:left += 1else:right -= 1return [-1, -1] # 題目保證有解，這行不會執行
? 為什么正確？ 每次移動都排除了大量不可能的解，縮小了搜索范圍。
? 其他應用：二分查找、反轉字符串、三數之和、盛最多水的容器。
3. 滑動窗口（也是雙指針的一種）
兩個指針形成一個窗口（區間），通過移動指針的起始位置來動態地擴展或收縮這個窗口。常用于子串、子數組問題。
典型問題：長度最小的子數組 (LeetCode 209)
題目：給定一個含有 n 個正整數的數組和一個正整數 target。找出該數組中滿足其和 ≥ target 的長度最小的連續子數組，并返回其長度。
? 思路：
? 使用兩個指針 left 和 right，代表窗口的左右邊界。? right 指針向右移動，擴大窗口，直到窗口內的元素總和 >= target。? 一旦滿足條件，記錄當前窗口長度，然后 left 指針向右移動，收縮窗口，嘗試尋找更小的窗口，同時更新窗口和。? 重復上述過程，直到 right 到達數組末尾。
? 代碼示例 (Python)
def minSubArrayLen(target: int, nums: List[int]) -> int:
left = 0
total = 0
min_len = float(‘inf’) # 初始化為一個極大值
# right指針遍歷整個數組，作為窗口的右邊界for right in range(len(nums)):total += nums[right] # 擴大窗口，加入right指向的元素# 當窗口總和滿足條件時，收縮左邊界while total >= target:# 更新最小長度current_len = right - left + 1min_len = min(min_len, current_len)# 縮小窗口，從總和里減去left指向的元素，并移動lefttotal -= nums[left]left += 1return 0 if min_len == float('inf') else min_len
? 其他應用：字符串的排列、找到字符串中所有字母異位詞、最小覆蓋子串。
三、總結與要點
類型 指針方向 典型應用 關鍵特點
快慢指針 同向，速度不同 鏈表判環，找中點 常用于鏈表數據結構
左右指針 相向而行 有序數組的兩數之和，反轉數組 序列有序是關鍵前提
滑動窗口 同向，一前一后 最小長度子數組，字符串匹配 維護一個動態變化的區間
使用雙指針法的核心要點：
- 分析問題特性：先思考暴力解法，再看數據是否有有序、單調性等特性，能否用指針移動來避免重復計算。
- 確定指針含義：明確每個指針代表什么（如鏈表的節點、數組的索引）。
- 確定移動規則：想清楚在什么條件下移動哪個指針，以及移動多少。
- 注意邊界條件：仔細處理指針越界、相遇、初始位置等情況。
希望這個詳細的講解能幫助你徹底理解雙指針法！多加練習是掌握它的最好方式。
