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

细节解析

这里有一个容易踩坑的地方：s.size() 返回的是 size_t（无符号类型），而 len 是 int。直接相减可能导致负数被解释为极大值。所以在循环条件中，我使用了 right + len <= n 这种形式，并提前将 s.size() 转为 int 赋值给 n，避免类型转换带来的潜在越界风险。

2. 最小覆盖子串

如果说上一题是'定长单词'的滑动窗口，这一题则是典型的'变长区间'问题。我们需要在字符串 s 中找到包含 t 所有字符的最短子串。

核心思路

使用双指针维护一个滑动窗口 [left, right]：

1. 右指针扩张：不断向右移动 right，将字符加入窗口，直到窗口包含了 t 的所有字符。
2. 左指针收缩：一旦满足条件，尝试移动 left 缩小窗口，同时保持满足条件，以更新最小长度。
3. 频次统计：用哈希表（或数组）记录 t 中字符的需求量和窗口中实际拥有的数量。

代码实现

为了提升效率，针对 ASCII 字符集，我们可以直接用长度为 128 的数组替代哈希表。

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++) {
            char c = s[right];
            hash2[c]++;
            
            // 当窗口中某字符数量达到需求时，有效种类数加一
            if(hash2[c] == hash1[c]) {
                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) : "";
    }
};

关键点总结

• 判断条件：不要每次循环都遍历哈希表比较，而是维护一个 count 变量。只有当某个字符的数量刚好从'不足'变为'满足'时，count 才增加；反之亦然。这样可以将时间复杂度优化到 O(N)。
• 数组优化：由于题目通常涉及 ASCII 字符，使用 int[128] 比 unordered_map 更快且更省内存。
• 边界处理：最后记得检查 begin 是否更新过，如果没有找到匹配子串，应返回空字符串。

这两道题是滑动窗口变种的典型代表。掌握它们的关键在于理解'窗口何时扩张、何时收缩'以及'如何高效判断窗口状态'。希望这些实战经验能帮你应对类似的字符串匹配挑战。