滑动窗口算法实战：串联所有单词子串与最小覆盖子串

流程解析

这里的关键在于理解为什么需要外层循环 i 从 0 到 len-1。因为合法的子串起始位置不一定对齐单词边界，比如单词长度为 3，合法子串可能从索引 1 开始。通过分情况讨论，我们覆盖了所有可能的对齐方式。

16. 最小覆盖子串

题目描述

给定字符串 s 和 t，找出 s 中包含 t 所有字符的最短子串。如果不存在则返回空串。

解题思路

这是滑动窗口的经典应用。我们需要动态维护一个窗口，使其包含 t 的所有字符且数量足够。

优化点在于使用定长数组代替哈希表。由于字符集通常是 ASCII，使用大小为 128 的数组可以显著提升性能。同时引入 count 变量记录当前窗口中满足频次要求的字符种类数，避免每次检查时遍历整个哈希表。

C++ 实现

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 记录 t 中字符频次
        int kinds = 0; // 记录 t 中不同字符的种类数
        
        for(char c : t) {
            if(hash1[c]++ == 0) {
                kinds++;
            }
        }
        
        int left = 0, right = 0;
        int count = 0; // 当前窗口满足条件的字符种类数
        int min_len = s.size() + 1;
        int begin = -1;
        int hash2[128] = {0}; // 记录窗口内字符频次
        
        for(right = 0; right < s.size(); right++) {
            hash2[s[right]]++;
            
            // 当窗口内某字符数量达到目标要求时，有效种类数加一
            if(hash2[s[right]] == hash1[s[right]]) {
                count++;
            }
            
            // 当所有字符种类都满足要求时，尝试收缩左边界
            while(count == kinds) {
                if(min_len > right - left + 1) {
                    min_len = right - left + 1;
                    begin = left;
                }
                
                // 准备移出左边界字符
                if(hash2[s[left]] == hash1[s[left]]) {
                    count--;
                }
                hash2[s[left]]--;
                left++;
            }
        }
        
        return begin != -1 ? s.substr(begin, min_len) : "";
    }
};

流程解析

注意 while(count == kinds) 这个循环。一旦满足条件，我们就立即尝试缩小窗口以寻找更优解。在收缩过程中，如果移出的字符导致该字符不再满足频次要求，count 就会减一，循环随即终止，继续向右扩展。这种'扩张 - 收缩'的机制保证了我们在 O(N) 时间内找到最优解。

这两道题展示了滑动窗口在处理字符串匹配时的灵活性。掌握核心逻辑后，针对具体约束调整窗口大小和判定条件即可应对变体。