【每日算法】Day 12-1：滑动窗口算法精讲——子串/子数组问题的优化利器（C++实现）

攻克子串问题的效率密码！今日深入解析滑动窗口算法的核心思想与实战技巧，覆盖最小覆盖子串、最长无重复子串等高频场景，彻底掌握O(n)时间复杂度的窗口滑动艺术。

---

一、滑动窗口核心思想

滑动窗口（Sliding Window） 是一种通过维护动态窗口解决子串/子数组问题的算法，核心特性：

1. 双指针驱动：左指针收缩窗口，右指针扩展窗口

2. 窗口单调性：窗口滑动过程保持单向性

3. 哈希表辅助：快速统计窗口内元素状态

适用场景：

• 连续子数组/子串的最值问题

• 统计满足特定条件的区间数量

• 字符串匹配与模式查找

与暴力解法的对比优势：

方法	时间复杂度	空间复杂度	适用数据规模
暴力枚举	O(n²)	O(1)	n < 10³
滑动窗口	O(n)	O(k)	n ≤ 10⁶

---

二、滑动窗口模板（C++）

通用模板结构

void slidingWindow(string s) {unordered_map<char, int> window; // 窗口状态记录int left = 0, right = 0;         // 双指针while (right < s.size()) {char c = s[right];right++;                    // 右扩窗口window[c]++;                // 更新状态while (窗口需要收缩条件) {   // 左缩窗口char d = s[left];left++;window[d]--;            // 更新状态}// 更新全局结果（位置取决于具体问题）}
}

关键参数：

• 窗口状态记录：哈希表/数组记录字符频率

• 收缩条件：触发窗口调整的阈值条件

• 结果更新时机：根据问题需求在适当位置更新结果

---

三、四大高频应用场景

场景1：最小覆盖子串（LeetCode 76）

string minWindow(string s, string t) {unordered_map<char, int> need, window;for (char c : t) need[c]++;int left = 0, right = 0;int valid = 0; // 匹配字符数int start = 0, len = INT_MAX;while (right < s.size()) {char c = s[right++];if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}while (valid == need.size()) { // 满足条件时收缩if (right - left < len) {  // 更新最小窗口start = left;len = right - left;}char d = s[left++];if (need.count(d)) {if (window[d] == need[d]) valid--;window[d]--;}}}return len == INT_MAX ? "" : s.substr(start, len);
}

场景2：最长无重复子串（LeetCode 3）

int lengthOfLongestSubstring(string s) {unordered_map<char, int> window;int left = 0, right = 0, max_len = 0;while (right < s.size()) {char c = s[right++];window[c]++;while (window[c] > 1) { // 出现重复char d = s[left++];window[d]--;}max_len = max(max_len, right - left);}return max_len;
}

场景3：长度最小的子数组（LeetCode 209）

int minSubArrayLen(int target, vector<int>& nums) {int left = 0, sum = 0, min_len = INT_MAX;for (int right = 0; right < nums.size(); ++right) {sum += nums[right];while (sum >= target) { // 满足条件时收缩min_len = min(min_len, right - left + 1);sum -= nums[left++];}}return min_len == INT_MAX ? 0 : min_len;
}

场景4：字符串排列（LeetCode 567）

bool checkInclusion(string s1, string s2) {unordered_map<char, int> need, window;for (char c : s1) need[c]++;int left = 0, right = 0, valid = 0;while (right < s2.size()) {char c = s2[right++];if (need.count(c)) {window[c]++;if (window[c] == need[c]) valid++;}while (right - left >= s1.size()) { // 窗口大小固定if (valid == need.size()) return true;char d = s2[left++];if (need.count(d)) {if (window[d] == need[d]) valid--;window[d]--;}}}return false;
}

四、滑动窗口变种与优化

变种类型	特点	经典问题
固定窗口	窗口大小固定	字符串排列、滑动窗口平均值
可变窗口	窗口大小动态变化	最小覆盖子串、最长子串
哈希表优化	用数组替代哈希表加速	ASCII字符集问题
前缀和+窗口	结合前缀和数组处理子数组和	和等于k的最长子数组

---

五、大厂真题实战

真题1：最大连续1的个数 III（某大厂2024面试）

题目描述：
二进制数组最多翻转k个0为1，求最长连续1子数组
滑动窗口解法：

int longestOnes(vector<int>& nums, int k) {int left = 0, max_len = 0, zero_count = 0;for (int right = 0; right < nums.size(); ++right) {if (nums[right] == 0) zero_count++;while (zero_count > k) { // 窗口内0超过k个if (nums[left] == 0) zero_count--;left++;}max_len = max(max_len, right - left + 1);}return max_len;
}

真题2：替换后的最长重复字符（LeetCode 424）

int characterReplacement(string s, int k) {vector<int> count(26, 0);int left = 0, max_count = 0, max_len = 0;for (int right = 0; right < s.size(); ++right) {count[s[right]-'A']++;max_count = max(max_count, count[s[right]-'A']);while (right - left + 1 - max_count > k) { // 需要替换超过k次count[s[left]-'A']--;left++;}max_len = max(max_len, right - left + 1);}return max_len;
}

六、复杂度与优化策略

操作	时间复杂度	空间复杂度	优化技巧
窗口滑动	O(n)	O(1)	数组替代哈希表
状态更新	O(1)	O(k)	位运算压缩状态
收缩检测	O(1)	O(1)	记录最大值避免全扫描

---

七、常见误区与调试技巧

1. 窗口收缩条件错误：未正确维护窗口有效性（如LeetCode 424中的替换次数计算）

2. 哈希表更新遗漏：左指针移动时未同步更新状态

3. 初始化错误：未正确初始化哈希表或计数器

4. 调试技巧：

   • 打印窗口左右边界及内部状态

   • 可视化窗口滑动过程

   • 添加断言检查窗口有效性

---

LeetCode真题训练：

• 438. 找到字符串中所有字母异位词

• 567. 字符串的排列

• 1004. 最大连续1的个数 III