滑动窗口通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
std::unordered_map<char, int> need, window;

// 1. 初始化 need（目标字符频率）
for (const auto& c : target) {
    need[c]++;
}

int left = 0, right = 0;
int valid = 0;  // 已匹配的字符种类数
// 根据题目需求自定义其他变量（如结果、长度等）

// 2. 移动 right 扩大窗口
while (right < s.size()) {
    char c = s[right];
    right++;
    
    // 3. 进行窗口内数据的更新
    if (need.count(c)) {
        window[c]++;
        if (window[c] == need[c]) {
            valid++;
        }
    }
    
    // 4. 判断是否需要收缩窗口
    while (窗口需要收缩的条件) {
        // 在这里更新结果（如果需要）
        
        // 5. 移动 left 缩小窗口
        char d = s[left];
        left++;
        
        // 6. 进行窗口内数据的更新
        if (need.count(d)) {
            if (window[d] == need[d]) {
                valid--;
            }
            window[d]--;
        }
    }
}

return res;

关键点说明

1️⃣ 窗口收缩条件（最重要的区别）

不同题目的收缩条件不同：

题目类型 收缩条件 何时更新结果
最小覆盖子串 valid == need.size() 收缩时（找最小）
字符串排列 right - left >= target.size() 收缩时（固定长度）
找所有异位词 right - left >= target.size() 收缩时（固定长度）
最长无重复子串 window[c] > 1（有重复） 扩张时（找最大）

2️⃣ 何时更新结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 情况1：求最小 → 在收缩窗口时更新
while (valid == need.size()) {  // 窗口合法
    res = min(res, right - left);  // 更新最小值
    // 然后收缩
}

// 情况2：求最大 → 在扩张窗口后更新
if (条件满足) {
    res = max(res, right - left);  // 更新最大值
}

// 情况3：固定长度 → 在收缩窗口时检查
while (right - left >= k) {
    if (valid == need.size()) {
        // 记录结果
    }
    // 收缩
}

三道经典题对比

🔹 最小覆盖子串 (LeetCode 76)

1
2
3
4
5
6
7
while (valid == need.size()) {  // 包含所有字符时收缩
    if (right - left < len) {   // 更新最小长度
        start = left;
        len = right - left;
    }
    // 收缩窗口...
}

🔹 字符串排列 (LeetCode 567)

1
2
3
4
5
while (right - left >= s1.size()) {  // 窗口达到目标长度时收缩
    if (valid == need.size())        // 检查是否匹配
        return true;
    // 收缩窗口...
}

🔹 找所有异位词 (LeetCode 438)

1
2
3
4
5
while (right - left >= p.size()) {
    if (valid == need.size())
        res.push_back(left);  // 记录起始位置
    // 收缩窗口...
}

核心思想

Note

基于这个框架，遇到子串/子数组相关的题目，只需要回答以下三个问题：
1、什么时候应该移动 right 扩大窗口？窗口加入字符时，应该更新哪些数据？
2、什么时候窗口应该暂停扩大，开始移动 left 缩小窗口？从窗口移出字符时，应该更新哪些数据？
3、什么时候应该更新结果？

  1. 右指针扩张：不断纳入新元素
  2. 左指针收缩：满足条件时尝试优化
  3. valid 计数：追踪匹配状态
  4. 灵活调整：根据题目需求调整收缩条件和结果更新时机