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

滑动窗口实战：两道经典字符串匹配题

在算法面试中，滑动窗口是处理连续子串或子数组问题的利器。今天我们来深入探讨两个高频考点：串联所有单词的子串和最小覆盖子串。这两道题虽然场景不同，但核心思想都是通过动态调整窗口边界来寻找最优解。

1. 串联所有单词的子串

这道题要求找到包含 words 列表中所有单词（每个单词长度相同）的起始位置。乍一看像是复杂的排列组合，但如果我们把每个单词看作一个'超级字符'，问题就简化成了寻找异位词的问题。

核心思路

关键在于理解窗口的移动方式：

• 既然每个单词长度固定为 len，那么窗口的左右指针每次移动的步长也应该是 len。
• 我们需要遍历整个字符串，但因为是从不同偏移量开始的，所以外层循环需要执行 len 次，分别以 0 到 len-1 作为起始偏移。
• 内部维护一个哈希表统计当前窗口内单词的出现次数，并与目标单词表的频次进行比对。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 统计目标单词频次
        
        for(auto& e : words) {
            hash1[e]++;
        }
        
        int len = words[0].size(); // 单词长度
        int m = words.size();      // 单词数量
        int n = s.size();          // 字符串总长度
        
        // 从 0 到 len-1 开始遍历，覆盖所有可能的起始偏移
        for(int i = 0; i < len; i++) {
            unordered_map<string, int> hash2; // 当前窗口单词频次
            int count = 0;                    // 有效单词计数
            int left = i;
            
            // 注意：right 每次增加 len
            for(int right = i; right + len <= n; right += len) {
                string str1 = s.substr(right, len);
                hash2[str1]++;
                
                // 如果当前单词在目标中存在且未超标，计入有效数
                if(hash2[str1] <= hash1[str1]) {
                    count++;
                }
                
                // 窗口大小超过所需范围，收缩左侧
                if(right - left + 1 > len * m) {
                    string str2 = s.substr(left, len);
                    if(hash2[str2] <= hash1[str2]) {
                        count--;
                    }
                    hash2[str2]--;
                    left += len;
                }
                
                // 如果有效单词数等于目标总数，记录结果
                if(count == m) {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

细节解析

这里有一个容易踩坑的地方：s.size() 返回的是 size_t（无符号类型），而 len 是 int。直接相减可能导致负数被解释为极大值。所以在循环条件中，我使用了 right + len <= n 这种形式，并提前将 s.size() 转为 int 赋值给 n，避免类型转换带来的潜在越界风险。

2. 最小覆盖子串

如果说上一题是'定长单词'的滑动窗口，这一题则是典型的'变长区间'问题。我们需要在字符串 s 中找到包含 t 所有字符的最短子串。

核心思路

使用双指针维护一个滑动窗口 [left, right]：

1. 右指针扩张：不断向右移动 right，将字符加入窗口，直到窗口包含了 t 的所有字符。
2. 左指针收缩：一旦满足条件，尝试移动 left 缩小窗口，同时保持满足条件，以更新最小长度。
3. 频次统计：用哈希表（或数组）记录 t 中字符的需求量和窗口中实际拥有的数量。

代码实现

为了提升效率，针对 ASCII 字符集，我们可以直接用长度为 128 的数组替代哈希表。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0}; // 记录 t 中字符需求
        int kinds = 0;        // 记录 t 中不同字符的种类数
        
        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++) {
            char c = s[right];
            hash2[c]++;
            
            // 当窗口中某字符数量达到需求时，有效种类数加一
            if(hash2[c] == hash1[c]) {
                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) : "";
    }
};

关键点总结

• 判断条件：不要每次循环都遍历哈希表比较，而是维护一个 count 变量。只有当某个字符的数量刚好从'不足'变为'满足'时，count 才增加；反之亦然。这样可以将时间复杂度优化到 O(N)。
• 数组优化：由于题目通常涉及 ASCII 字符，使用 int[128] 比 unordered_map 更快且更省内存。
• 边界处理：最后记得检查 begin 是否更新过，如果没有找到匹配子串，应返回空字符串。

这两道题是滑动窗口变种的典型代表。掌握它们的关键在于理解'窗口何时扩张、何时收缩'以及'如何高效判断窗口状态'。希望这些实战经验能帮你应对类似的字符串匹配挑战。