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

注意事项

• s.size() 返回 size_t（无符号），与 int 运算时需注意类型转换，避免负数溢出。
• 每轮循环必须重置 hash2，防止上一轮数据干扰。

16. 最小覆盖子串

题目描述

给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果不存在这样的子串，返回空串。

解题思路

典型的滑动窗口问题。使用两个指针维护窗口范围，动态调整左右边界以找到满足条件的最短区间。

核心逻辑：

1. 用哈希表记录 t 中字符需求。
2. 右指针扩展窗口，直到满足条件。
3. 左指针收缩窗口，在满足条件的前提下尽可能缩小。
4. 优化：对于 ASCII 字符，可用数组替代哈希表提升效率。

C++ 代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 记录 t 中字符需求
        int kinds = 0; // 需要匹配的字符种类数
        
        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) : "";
    }
};

流程解析

• 初始化：统计目标串 t 的字符频次及种类数。
• 扩张：右指针向右移动，更新窗口内字符计数，检查是否满足条件。
• 收缩：一旦满足条件，左指针向右移动，直到不再满足，期间记录最优解。
• 结果：根据记录的起始位置和长度截取子串。

这种基于数组的优化方案比纯哈希表更快，因为避免了 map 的查找开销，适合字符集有限的场景。