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

滑动窗口的核心思想

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

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

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