滑动窗口算法详解与 LeetCode 高频题目解题模板

滑动窗口算法详解

**滑动窗口（Sliding Window）**是解决数组或字符串子区间问题的利器。无论是'最小覆盖子串'，还是'长度最小的子数组'，滑动窗口都能以 O(n) 的时间复杂度优雅解决。

1. 为什么要学滑动窗口？

LeetCode 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组 [4,3] 是该条件下的长度最小的子数组。

暴力解法思路

1. 枚举所有可能的子数组
2. 计算每个子数组的和
3. 找出满足条件的最短子数组

// 暴力解法 O(n²)
int minSubArrayLen_brute(int target, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;
    // 枚举所有起始位置
    for (int i = 0; i < n; i++) {
        int sum = 0;
        // 枚举所有结束位置
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum >= target) {
                minLen = min(minLen, j - i + 1);
                break; // 找到了就 break，因为后面的更长
            }
        }
    }
    return minLen == INT_MAX ? 0 : minLen;
}

暴力解法的问题分析

当 n=10000 时，需要约 1 亿次操作，严重超时。

滑动窗口的优化思路

观察：窗口的连续性

假设我们有一个窗口 [2,3,1] 和为 6 < 7。

• 传统做法： 丢弃整个窗口，从 3 重新开始。
• 聪明做法： 为什么不只丢弃左边的 2，保留 [3,1] 呢？

当前窗口：[2,3,1] 和=6 < 7 扔掉左边：移除 2 → [3,1] 和=4 加入右边：加入 2 → [3,1,2] 和=6 加入右边：加入 4 → [3,1,2,4] 和=10 ≥ 7 这样避免了重复计算 [3,1] 的和！

滑动窗口的核心思想

就像相机取景框，只移动边界，不重新拍摄整个画面。

int minSubArrayLen_sliding(int target, vector<int>& nums) {
    int left = 0;       // 窗口左边界
    int sum = 0;        // 当前窗口的和
    int minLen = INT_MAX; // 最小长度
    int n = nums.size();
    
    for (int right = 0; right < n; right++) {
        // 1. 加入右边元素（扩大窗口）
        sum += nums[right];
        
        // 2. 当窗口满足条件时，尝试收缩窗口
        while (sum >= target) {
            // 更新最小长度
            minLen = min(minLen, right - left + 1);
            // 收缩窗口：移除左边元素
            sum -= nums[left];
            left++;
        }
        // 3. 如果窗口不满足条件，继续扩大窗口（下一轮循环）
    }
    return minLen == INT_MAX ? 0 : minLen;
}

先向右扩大，当 sum 足够时，再从左缩小。

2. 滑动窗口的核心思想

四大核心理念

1. 连续性原则

只处理连续的子序列，不是任意的子集。

• ✅ [1,2,3,4] 中的 [2,3,4]（连续，可以用滑动窗口）
• ❌ [1,2,3,4] 中的 [1,3,4]（不连续，不能用滑动窗口）

2. 单调移动原则

左右指针只能单向移动（通常向右）。

int left = 0, right = 0;
while (right < n) {
    // right 只会增加
    // left 只会增加或不变
    // 永远不会回头！
}

3. 局部更新原则

窗口从 [2,3,1] 滑动到 [3,1,2]。

• 传统方法：重新计算 3+1+2 = 6
• 滑动窗口：利用已有的 2+3+1=6，然后 new_sum = old_sum - 离开的元素 + 新进入的元素 = 6 - 2 + 2 = 6
• 只计算变化的部分！

4. 最优性保证原则

通过合理的收缩规则，确保不会错过最优解。

while (窗口不满足条件) {
    收缩窗口; // 剔除"坏"元素
}
// 此时窗口是当前右边界下的"局部最优"

3. LeetCode 题目实战

1. 代码实现：最长无重复子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.size(); right++) {
            while (charSet.find(s[right]) != charSet.end()) {
                charSet.erase(s[left]);
                left++;
            }
            charSet.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

set 是 C++ STL 中的一种关联容器，它存储唯一的元素（不允许重复），并且元素会自动排序。

• #include <set>：有序集合（基于红黑树实现）
• #include <unordered_set>：无序集合（基于哈希表实现）

大致思路

1. 用一个 unordered_set 来记录当前窗口里的字符，保证里面没有重复。
2. 用双指针 left、right 表示窗口的左右边界，left 初始为 0。
3. 用 maxLen 记录遍历过程中最长的无重复子串长度。
4. right 从左到右遍历字符串，每次尝试把 s[right] 加入窗口。
5. 如果发现 s[right] 已经在 set 里（重复了），就不断从左边 erase 字符、left++，直到把重复的那个字符彻底移出窗口。
6. 把当前 s[right] 加入 set，更新窗口长度，维护 maxLen。
7. 遍历结束后，maxLen 就是答案。

重点讲解 while 循环

它的作用是：当遇到重复字符时，持续移动左指针，直到移除那个重复字符。

例子：s = "abcbda"

我们用滑动窗口 [left, right] 来跟踪当前无重复字符的子串。

步骤分析：

1. 初始状态：left = 0, charSet = {}
2. right = 0：'a' 不在集合中，直接加入 → charSet = {'a'}, 长度=1
3. right = 1：'b' 不在集合中，直接加入 → charSet = {'a', 'b'}, 长度=2
4. right = 2：'c' 不在集合中，直接加入 → charSet = {'a', 'b', 'c'}, 长度=3
5. right = 3：'b' 已经在集合中！
   • 进入 while 循环
   • 第一次循环：移除 s[left]（即 s[0] = 'a'），left = 1
   • 检查 'b' 还在集合中吗？是的，因为集合现在是 {'b', 'c'}
   • 第二次循环：移除 s[left]（即 s[1] = 'b'），left = 2
   • 现在集合是 {'c'}，'b' 不在集合中了
   • 退出 while 循环
   • 加入 'b'，集合变为 {'c', 'b'}，长度 = right - left + 1 = 3 - 2 + 1 = 2
6. right = 4：'d' 不在集合中，直接加入 → charSet = {'c', 'b', 'd'}, 长度=3

后续步骤依此类推，最终返回最大长度。