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

细节解析

在实际运行中，最容易踩坑的是 size() 的类型问题。std::string::size() 返回无符号整数 size_t，如果直接减去 len 可能导致下溢变成极大值。因此代码中显式强转为 int 并采用 right + len <= s.size() 的判断方式更为安全。

16. 最小覆盖子串

题目描述

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

核心思路

这是一个典型的动态窗口收缩问题。我们需要维护两个状态：

1. 目标串 t 中各字符的需求频次。
2. 当前窗口内已满足的字符频次。

当窗口内包含的字符种类和数量都满足 t 的要求时，尝试收缩左边界以寻找更优解。

优化策略

虽然可以使用 unordered_map 来处理字符映射，但在 ASCII 字符集范围内，使用定长数组（如 int[128]）替代哈希表能显著提升性能，减少内存分配开销。

代码实现

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

流程总结

1. 初始化：统计目标串字符频次，确定需要匹配的种类数 kinds。
2. 扩张右指针：将字符加入窗口，若该字符频次达标，则更新 count。
3. 收缩左指针：一旦 count == kinds，说明找到可行解。此时记录长度，并尝试移除左侧字符。若移除后某字符不再达标，则停止收缩，继续扩张右指针。
4. 结果提取：遍历结束后，根据记录的起始位置和长度截取子串。

这种双指针配合数组哈希的方法，时间复杂度为 O(N)，空间复杂度为 O(1)（固定 128 大小），是处理此类字符统计问题的标准最优解。