雙指針與滑動窗口算法精講：從原理到高頻面試題實戰

引言：算法選擇的十字路口

????????在算法面試中，雙指針和滑動窗口如同兩把瑞士軍刀，能高效解決80%以上的數組和字符串問題。本文將深入解析這兩種技術的核心差異，結合力扣高頻題目，提供可直接復用的代碼。

一、算法核心思想解析

1. 雙指針技術

????????雙指針算法是通過維護?兩個指針變量?（通常為數組/鏈表索引）協同遍歷數據結構的高效策略，主要用于優化暴力解法的時空復雜度。

?三種經典模式?：

?對撞指針?：首尾指針向中間收斂（如三數之和）
?快慢指針?：同向移動但速度不同（如環形鏈表檢測）
?滑動窗口?：動態維護子區間（特殊雙指針實現）

2. 滑動窗口技術

????????作為雙指針的特殊形式，滑動窗口具有以下特點：

兩個指針?同向移動?且?維護一個連續區間
通過窗口擴張/收縮動態調整解空間

3. 算法特性對比

特性	雙指針算法	滑動窗口算法
?指針移動方向?	可對撞/同向	嚴格同向移動
?數據要求?	常需排序	原始數據即可
?時間復雜度?	O(n)~O(n2)	O(n)
?典型問題?	有序數組組合問題	子串/子數組最優解
?狀態維護?	通常不需要	需要哈希表記錄狀態

二、高頻面試題分類精講

1. 雙指針經典題型：三數之和（LeetCode 15）

解題思路：

1. 暴力解法（不推薦）

最直觀的方法是三重循環遍歷所有可能的三元組，時間復雜度為O(n3)，效率太低。

2. 排序 + 雙指針法（推薦）

?步驟如下：?

?排序數組?：首先將數組排序，這樣可以利用有序性來優化搜索
?固定一個數?：遍歷數組，將當前元素作為第一個數
?雙指針搜索?：在當前元素后面的部分使用雙指針（左指針從當前元素后一位開始，右指針從數組末尾開始）尋找另外兩個數
?去重處理?：跳過重復的元素以避免重復解

?時間復雜度?：O(n2)（排序O(nlogn) + 雙指針遍歷O(n2)）

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int length = nums.length;if (nums == null || length < 3) {return result;}Arrays.sort(nums);  // 關鍵步驟：排序for (int i =0; i < length; i++) {// 需要和上一次枚舉的數不相同if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i+1;int right = length - 1;int target = -nums[i]; // nums[left] + nums[right] = targetwhile(left < right) {int sum = nums[left] + nums[right];if (sum == target) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳過重復的left和rightwhile (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;} else if (sum < target) {left++;} else {right--;}}}return result;}

2. 滑動窗口經典題型：最小覆蓋子串（LeetCode 76）

算法核心思想

? 滑動窗口（Sliding Window）算法?是解決最小覆蓋子串問題的最優方法：

?雙指針定義窗口?：使用left和right兩個指針表示當前考察的子串窗口
?哈希表記錄需求?：使用兩個哈希表分別存儲：

need：目標字符串T中各字符的需求量
window：當前窗口中滿足需求的字符數量

? ? ? 3. 動態擴展收縮窗口?：

先擴展right指針尋找可行解
再收縮left指針優化解

? ? ? 4.?有效字符計數?：通過valid變量統計窗口中已滿足需求的字符種類數

? ? ? 5. 實時更新結果?：每當找到更小的滿足條件的子串時更新結果

復雜度分析

?時間復雜度?：O(n)，其中n是字符串S的長度
?空間復雜度?：O(m)，其中m是字符集大小（通常為常數級）

Java實現代碼

public String minWindow(String s, String t) {// 邊界條件檢查if (s == null || t == null || s.length() < t.length()) {return "";}// 初始化需求哈希表，記錄t中每個字符出現的次數Map<Character, Integer> need = new HashMap<>();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}// 初始化窗口哈希表，記錄當前窗口中滿足需求的字符數量Map<Character, Integer> window = new HashMap<>();// 記錄窗口中滿足need條件的字符個數int valid = 0;// 記錄最小覆蓋子串的起始位置和長度int start = 0, minLen = Integer.MAX_VALUE;// 滑動窗口左右指針int left = 0, right = 0;while (right < s.length()) {// 獲取右指針當前字符char c = s.charAt(right);// 右指針向右移動right++;// 如果當前字符在需求表中，則更新窗口計數if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);// 如果窗口中該字符數量等于需求數量，則valid加1if (window.get(c).equals(need.get(c))) {valid++;}}// 當窗口滿足所有字符需求時，嘗試收縮左邊界while (valid == need.size()) {// 更新最小覆蓋子串信息if (right - left < minLen) {start = left;minLen = right - left;}// 獲取左指針當前字符char d = s.charAt(left);// 左指針向右移動left++;// 如果移出的字符在需求表中，則更新窗口計數if (need.containsKey(d)) {// 如果窗口中該字符數量剛好等于需求數量，則valid減1if (window.get(d).equals(need.get(d))) {valid--;}window.put(d, window.get(d) - 1);}}}// 返回最小覆蓋子串，如果沒有找到則返回空字符串return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}

三、算法選擇的核心判別特征

1. 雙指針算法的識別特征

當問題呈現以下?至少兩個?特征時，優先考慮雙指針算法：

?線性序列結構?（數組/鏈表）
- 典型表現：輸入數據為數組或鏈表等線性結構
- 反例：樹形結構或圖結構通常不適用
?有序性或可排序性?
- 典型表現：題目明確說明"已排序"或允許預處理排序
- 示例特征："非遞減順序排列"、"你可以假設數組已經按升序排列"
?對稱性/雙向操作需求?
- 典型表現：需要從兩端向中間或特定方向協同操作
- 示例場景：回文判斷、盛水容器問題
?組合優化問題?
- 典型表現：需要尋找兩個或多個元素的特定組合
- 示例模式："找出滿足條件的兩個元素"、"確定三個數的組合"

2. 滑動窗口算法的識別特征

當問題呈現以下?至少兩個?特征時，優先考慮滑動窗口算法：

?連續子區間要求?
- 典型表現：需要處理數組中連續的序列或子串
- 關鍵詞："連續子數組"、"子串"、"連續的...滿足條件"
?窗口可變或固定大小?
- 典型表現：需要動態調整或保持固定大小的區間
- 可變窗口特征："最短/最長滿足條件的..."
- 固定窗口特征："大小為k的..."
?統計類約束條件?
- 典型表現：基于頻率、和、平均值等統計量的條件判斷
- 示例條件："包含所有字符"、"和≥target"、"無重復字符"
?最優解搜索?
- 典型表現：需要尋找滿足特定條件的最優區間
- 典型目標："最小的...滿足..."、"最大的...滿足..."