雙指針思想介紹

雙指針（Two Pointers）是一種在數組或鏈表等線性結構中常用的算法技巧，通過使用兩個指針（索引或引用）以不同的速度或方向遍歷數據結構，從而高效解決問題。雙指針通常用于優化暴力解法，將時間復雜度從 O(n2) 降低到 O(n) 或 O(n log n)。

常見應用場景：

1. ?快慢指針：用于鏈表中的環檢測、找中點等（如快指針每次走兩步，慢指針走一步）。
2. ?左右指針：用于有序數組的兩數之和、反轉數組等（如一個指針從左向右，另一個從右向左）。
3. ?滑動窗口：通過調整兩個指針的間隔解決子數組/子串問題（如最小覆蓋子串）。

---

藍橋杯中的雙指針題目示例

以下是藍橋杯競賽中可能用到雙指針思想的題目及其解法思路：

1. ?兩數之和（有序數組）?

• ?題目描述：給定一個升序排列的數組和一個目標值，找到數組中兩個數的和等于目標值，返回它們的索引。
• ?雙指針解法：
  • 初始化左指針?left = 0，右指針?right = len(nums) - 1。
  • 比較?nums[left] + nums[right]?與目標值：
    • 若和等于目標值，返回結果；
    • 若和小于目標值，left++（需要更大的數）；
    • 若和大于目標值，right--（需要更小的數）。
• ?時間復雜度：O(n)。

def twoSum(nums, target):left, right = 0, len(nums) - 1while left < right:s = nums[left] + nums[right]if s == target:return [left, right]elif s < target:left += 1else:right -= 1return []

2. ?三數之和（去重）?

• ?題目描述：找到數組中所有不重復的三元組，滿足?a + b + c = 0。
• ?雙指針解法：
  • 先排序數組，固定一個數?nums[i]，然后用雙指針在?i+1?到末尾尋找兩數之和等于?-nums[i]。
  • 需跳過重復值以避免重復解。
• ?時間復雜度：O(n2)。

python

復制

def threeSum(nums):nums.sort()res = []for i in range(len(nums) - 2):if i > 0 and nums[i] == nums[i - 1]:continue  # 去重left, right = i + 1, len(nums) - 1while left < right:s = nums[i] + nums[left] + nums[right]if s < 0:left += 1elif s > 0:right -= 1else:res.append([nums[i], nums[left], nums[right]])while left < right and nums[left] == nums[left + 1]:left += 1  # 去重while left < right and nums[right] == nums[right - 1]:right -= 1  # 去重left += 1right -= 1return res

3. ?盛最多水的容器（貪心+雙指針）?

• ?題目描述：給定一個數組表示容器的高度，找到兩條線使得它們與 x 軸構成的容器能裝最多的水。
• ?雙指針解法：
  • 初始化?left = 0，right = len(height) - 1，max_area = 0。
  • 每次移動較短的邊（因為移動長邊不可能增加面積）。
• ?時間復雜度：O(n)。

python

復制

def maxArea(height):left, right = 0, len(height) - 1max_area = 0while left < right:area = (right - left) * min(height[left], height[right])max_area = max(max_area, area)if height[left] < height[right]:left += 1else:right -= 1return max_area

4. ?藍橋杯真題示例：日志統計（滑動窗口）?

• ?題目鏈接：藍橋杯 2018 省賽
• ?問題描述：給定 N 條日志的點贊時間，統計在任意長度為 D 的時間段內點贊不少于 K 次的帖子。
• ?雙指針解法：
  • 按時間排序后，用滑動窗口（雙指針）統計窗口內的點贊數，若滿足條件則標記帖子。
• ?代碼片段：

  python

  復制

  logs = [...]  # 日志數據格式: [(時間, 帖子id), ...]
  logs.sort()
  count = {}  # 記錄當前窗口內各id的點贊數
  res = set()
  left = 0
  for right in range(len(logs)):id = logs[right][1]count[id] = count.get(id, 0) + 1while logs[right][0] - logs[left][0] >= D:count[logs[left][1]] -= 1left += 1if count[id] >= K:res.add(id)

---

總結

雙指針的核心是通過協同移動兩個指針減少不必要的計算，常用于：

• 有序數組的搜索（如兩數之和）。
• 滑動窗口問題（如子串、區間統計）。
• 鏈表操作（如快慢指針）。

在藍橋杯競賽中，雙指針常與排序、貪心等結合，需注意邊界條件和去重處理。