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

流程解析

16. 最小覆盖子串

题目链接

LeetCode 76 - 最小覆盖子串

题目描述

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

题目示例

解法思路

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

优化点：

1. 双哈希表：一个记录目标串 t 的需求，另一个记录当前窗口的状态。
2. 计数优化：使用 count 变量记录当前窗口中已满足频次要求的字符种类数，避免每次循环都遍历整个哈希表。
3. 数组替代 Map：对于 ASCII 字符，直接使用长度为 128 的数组模拟哈希表，性能更优。

算法流程

1. 初始化两个数组（或哈希表），分别统计 t 的字符需求和当前窗口的字符情况。
2. 右指针向右扩展，直到窗口满足条件。
3. 一旦满足条件，尝试收缩左指针以找到最小窗口，同时更新最优解。
4. 重复上述过程直到右指针遍历结束。

C++ 代码实现

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++;
            }
        }
        
        if(begin != -1) {
            return s.substr(begin, min_len);
        }
        return "";
    }
};

流程解析

总结

这两道题展示了滑动窗口在处理字符串匹配时的灵活性。第一题通过调整窗口步长和多次遍历解决了变体问题；第二题则通过数组优化和计数器技巧实现了空间与时间的双重提升。掌握这些模式后，面对类似的区间覆盖或子串查找问题，就能快速构建解题框架。