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

算法流程解析

16. 最小覆盖子串

题目链接

76. 最小覆盖子串 - 力扣（LeetCode）

题目描述

题目示例

解法思路

算法思路

研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。

如何判断当前窗口的所有字符是符合要求的呢？

• 我们可以使用两个哈希表。其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。
• 当动态哈希表中包含目标串中所有字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是一种可行的方案。

算法流程

1. 定义两个全局的哈希表：hash1 用来记录子串的信息，hash2 用来记录目标串 t 的信息；
2. 实现一个接口函数，判断当前窗口是否满足要求：
   • 遍历两个哈希表中对应位置的元素
   • 如果 t 中某个字符的数量大于窗口中字符的数量，说明不匹配，返回 false。
   • 如果全部匹配，返回 true。

主函数中：

1. 先将 t 的信息放入 hash2 中；
2. 初始化一些变量：左右指针 left = 0，right = 0；目标子串的长度 min_len = INT_MAX；目标子串的起始位置 begin；
3. 当 right 小于字符串 s 的长度时，一直循环：
   • 将当前遍历到的元素扔进 hash1 中；
   • 检测当前窗口是否满足条件；
   • 如果满足条件：判断当前窗口是否变小。如果变小：更新长度 min_len，以及字符串的起始位置 begin；判断完毕后，将左侧的元素滑出窗口，顺便更新到 hash1；重复上述两个过程，直到窗口不满足条件；
   • right++，遍历下一个元素；
4. 判断 min_len 的长度是否等于 INT_MAX；
   • 如果相等，说明没有匹配，返回空串；
   • 如果不相等，说明匹配，返回 s 中从 begin 位置往后 min_len 长度的字符串。

代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        // 优化：数组模拟实现哈希表，count 标记'有效字符'的种类
        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;
        string ret;
        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) {
            ret = s.substr(begin, min_len);
        }
        return ret;
    }
};

算法流程解析