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

最小覆盖子串

题目要求

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

解题思路

这是一个经典的滑动窗口问题。我们需要动态维护一个窗口，使其包含 t 的所有字符。

核心逻辑是使用两个哈希表（或定长数组）：

• hash1 记录目标字符串 t 中每个字符的需求频次。
• hash2 动态记录当前窗口内字符的实际频次。

当 hash2 中某个字符的数量达到 hash1 的要求时，说明该字符已满足条件。我们可以用一个计数器 count 来跟踪当前窗口满足了多少种字符的需求。一旦 count 等于 t 中不同字符的种类数，说明当前窗口是合法的，此时尝试收缩左边界以寻找更小的合法窗口。

代码实现

这里提供两个版本，初版使用 unordered_map，优化版使用定长数组以提升性能。

初版（基于哈希表）

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash1; // 记录 t 中字符频次
        for (auto &ch : t) hash1[ch]++;
        
        unordered_map<char, int> hash2; // 记录窗口内字符频次
        int n = hash1.size();
        int m = s.size();
        int len = INT_MAX;
        int reti = 0;
        int count = 0;
        
        for (int left = 0, right = 0; right < m; right++) {
            char inChar = s[right];
            hash2[inChar]++;
            
            // 如果当前字符在 t 中且数量刚好满足需求，计数加一
            if (hash1.count(inChar) && hash2[inChar] == hash1[inChar]) {
                count++;
            }
            
            // 当所有字符都满足需求时，尝试收缩窗口
            while (count == n) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    reti = left;
                }
                
                char outChar = s[left++];
                if (hash1.count(outChar) && hash2[outChar] == hash1[outChar]) {
                    count--;
                }
                hash2[outChar]--;
            }
        }
        
        return len == INT_MAX ? "" : s.substr(reti, len);
    }
};

优化版（基于定长数组）

对于 ASCII 字符，直接使用大小为 128 的数组替代哈希表可以显著减少内存开销和查找时间。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 统计字符串 t 中每一个字符的频次
        int kinds = 0;        // 统计有效字符有多少种
        for (auto ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }
        
        int hash2[128] = {0}; // 统计窗口内每个字符的频次
        int minlen = INT_MAX;
        int begin = -1;
        int count = 0;
        
        for (int left = 0, right = 0; right < s.size(); right++) {
            char inChar = s[right];
            // 进窗口 + 维护 count
            if (++hash2[inChar] == hash1[inChar]) count++;
            
            while (count == kinds) { // 判断条件
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                
                char outChar = s[left++];
                // 出窗口 + 维护 count
                if (hash2[outChar]-- == hash1[outChar]) count--;
            }
        }
        
        return begin == -1 ? "" : s.substr(begin, minlen);
    }
};

总结

这两道题都是滑动窗口的经典应用。第一题的关键在于理解'单词级'的窗口移动和多次遍历的必要性；第二题则展示了如何通过双指针配合哈希结构高效地维护区间状态。在实际工程中，如果字符集固定，优先使用数组代替哈希表往往能获得更好的性能表现。