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

流程解析

实际运行时，外层循环负责处理不同的起始偏移量，内层循环维护窗口。当窗口内某个单词数量超过需求时，虽然 count 不会增加，但我们需要通过移动左指针来保证窗口大小不超过 len * m，从而维持窗口的有效性。

2. 最小覆盖子串

题目链接： 76. 最小覆盖子串 - 力扣

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

题目示例：

解法思路

这是滑动窗口的经典应用。我们需要动态维护一个区间 [left, right]，使其包含 t 中的所有字符。

核心逻辑如下：

1. 双哈希表（或数组）：一个记录 t 的需求，一个记录当前窗口的状态。
2. 满足条件判断：当窗口内字符种类及数量都满足 t 的要求时，尝试收缩左边界以寻找更优解。
3. 空间优化：由于字符集通常是 ASCII，使用长度为 128 的数组替代 unordered_map 可以显著提升性能。

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, 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]]++; // 进窗口
            
            // 只有当该字符在 t 中存在且当前数量未超标时，才算作有效贡献
            if(hash2[s[right]] == hash1[s[right]]) {
                count++;
            }
            
            // 当所有种类字符都满足要求时，尝试收缩左边界
            while(count == kinds) {
                if(min_len > right - left + 1) {
                    min_len = right - left + 1;
                    begin = left;
                }
                
                // 准备移出 left 位置的字符
                if(hash2[s[left]] == hash1[s[left]]) {
                    count--;
                }
                hash2[s[left]]--;
                left++;
            }
        }
        
        return begin != -1 ? s.substr(begin, min_len) : "";
    }
};

流程解析

这里有一个细节：hash2[s[right]] == hash1[s[right]] 这个判断。它意味着当前加入的字符刚好补齐了该字符所需的数量。一旦超过这个数量，再添加同种字符也不会增加 count，这保证了我们只统计'有效'的字符种类。

总结

这两道题展示了滑动窗口在处理字符串匹配时的强大能力。

• 串联所有单词的子串：关键在于将单词视为原子单位，通过固定步长和多次遍历解决错位问题。
• 最小覆盖子串：重点在于如何高效判断窗口是否满足条件，利用数组优化哈希表是面试中的加分项。

掌握这两种模式，能帮你应对大部分涉及连续子串优化的算法面试题。