C/C++滑動窗口算法深度解析與實戰指南

引言

滑動窗口算法是解決數組/字符串連續子序列問題的利器，通過動態調整窗口邊界，將暴力解法的O(n2)時間復雜度優化至O(n)。本文將系統講解滑動窗口的核心原理、C/C++實現技巧及經典應用場景，助您掌握這一高效算法。

一、算法核心原理

1.1 窗口雙指針模型

• 左右指針：使用left和right指針界定窗口邊界
• 動態調整：
  • 擴展窗口：右指針右移擴大窗口范圍
  • 收縮窗口：當條件不滿足時左指針右移縮小窗口
• 狀態維護：通過哈希表/數組記錄窗口內元素狀態

1.2 兩種窗口類型

窗口類型	特點	典型場景
固定窗口	窗口大小恒定	滑動平均值、固定長度子數組
可變窗口	窗口大小動態調整	最長無重復子串、最小覆蓋子串

二、C/C++實現詳解

2.1 固定窗口實現模板

int fixedWindow(vector<int>& nums, int k) {int sum = 0, max_sum = 0;// 初始化窗口for (int i = 0; i < k; ++i) sum += nums[i];max_sum = sum;// 滑動窗口for (int right = k; right < nums.size(); ++right) {sum += nums[right] - nums[right - k];  // 滾動更新max_sum = max(max_sum, sum);}return max_sum;
}

2.2 可變窗口實現模板

int variableWindow(string s) {unordered_map<char, int> window;int left = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {char c = s[right];window[c]++;  // 擴展窗口// 收縮條件：出現重復字符while (window[c] > 1) {char d = s[left];window[d]--;  // 移出左邊界left++;}max_len = max(max_len, right - left + 1);  // 更新結果}return max_len;
}

三、經典問題解析

3.1 無重復字符的最長子串（LeetCode 3）

int lengthOfLongestSubstring(string s) {vector<int> char_map(128, -1);  // ASCII映射表int max_len = 0, left = 0;for (int right = 0; right < s.size(); ++right) {if (char_map[s[right]] >= left) {left = char_map[s[right]] + 1;  // 跳躍收縮}char_map[s[right]] = right;  // 更新最新位置max_len = max(max_len, right - left + 1);}return max_len;
}

3.2 最小覆蓋子串（LeetCode 76）

string minWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, valid = 0, start = 0, min_len = INT_MAX;for (int right = 0; right < s.size(); ++right) {char c = s[right];if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}// 收縮窗口while (valid == need.size()) {if (right - left + 1 < min_len) {min_len = right - left + 1;start = left;}char d = s[left++];if (need.count(d)) {if (window[d] == need[d]) valid--;window[d]--;}}}return min_len == INT_MAX ? "" : s.substr(start, min_len);
}

四、性能優化技巧

4.1 空間優化

• 數組替代哈希表：當字符集確定時（如ASCII），使用數組存儲頻次

  int char_count[128] = {0};  // 替代unordered_map
  

4.2 時間優化

• 跳躍收縮：發現重復元素時直接跳轉到重復位置+1
• 提前終止：當窗口長度已達理論最大值時break

五、復雜度分析

場景	時間復雜度	空間復雜度
固定窗口	O(n)	O(1)
可變窗口（哈希表）	O(n)	O(Σ)
可變窗口（數組）	O(n)	O(1)

六、應用場景拓展

1. 字符串處理：

   • 字母異位詞檢測
   • DNA序列分析
   • 回文子串查找

2. 數組問題：

   • 最大連續1的個數
   • 乘積小于K的子數組
   • 股票買賣時機分析

3. 數據流處理：

   • 實時移動平均值計算
   • 異常值檢測

七、常見錯誤避坑指南

1. 指針越界：確保left <= right且right < n
2. 狀態殘留：窗口收縮后需及時更新狀態變量
3. 循環條件：可變窗口必須使用while收縮而非if
4. 初始值設置：max_len應初始化為0而非INT_MIN

結語

滑動窗口算法通過精妙的指針操作，將復雜度從平方級別降至線性，是解決連續子序列問題的首選方案。掌握其核心思想與實現技巧，您將能高效解決LeetCode 3、76、209等經典題目。建議通過大量練習加深理解，特別是對窗口收縮條件的判斷和狀態維護的細節處理。