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

15. 串联所有单词的子串

题目描述： 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好由 words 中所有单词串联组成的子串的起始索引。

解法（滑动窗口 + 哈希表）：

算法思路

将每个单词视为一个整体字符，问题转化为寻找包含特定频次单词组合的区间。核心差异在于处理对象从字符变成了单词。

• 哈希表结构：使用 unordered_map<string, int> 统计目标单词频次。
• 步长控制：左右指针移动步长为单词长度 len。
• 遍历次数：由于起始位置可能不同，需执行 len 次滑动窗口遍历，确保不遗漏任何偏移量。

C++ 算法代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次
        for (auto &w : words) hash1[w]++;
        
        int len = words[0].size(), m = words.size();
        if (m == 0 || len == 0 || s.empty()) return ret;

        // 执行 len 次，覆盖所有可能的起始偏移
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash2; // 维护窗口内单词的频次
            int count = 0;
            
            for (int left = i, right = i; right + len <= s.size(); right += len) {
                string in = s.substr(right, len);
                hash2[in]++;
                
                // 进窗口 + 维护 count
                if (hash1.count(in) && hash2[in] <= hash1[in]) {
                    count++;
                }
                
                // 判断窗口是否过大
                if (right - left + 1 > len * m) {
                    string out = s.substr(left, len);
                    // 出窗口 + 维护 count
                    if (hash1.count(out) && hash2[out] <= hash1[out]) {
                        count--;
                    }
                    hash2[out]--;
                    left += len;
                }
                
                if (count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

算法总结

通过控制窗口大小和步长，配合哈希表统计频次，可以高效定位满足条件的子串。注意边界条件处理，如空字符串或空单词列表的情况。

---

16. 最小覆盖子串

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

解法（滑动窗口 + 哈希表）：

算法思路

研究对象是连续区间，适合用滑动窗口。关键在于如何快速判断当前窗口是否满足要求。

• 双哈希表策略：一个记录目标串 t 的字符频次，另一个动态维护窗口内的字符频次。
• 匹配判定：当窗口内某字符数量达到目标频次时，该字符才算'有效'。当所有有效字符种类数等于 t 的种类数时，窗口即满足条件。

算法流程

1. 初始化两个哈希表（或数组），分别统计 t 和窗口内容。
2. 右指针向右扩展，更新窗口状态。
3. 一旦满足条件，尝试收缩左指针以寻找更优解。
4. 记录满足条件下的最小窗口起始位置和长度。

C++ 算法代码

初版（基于 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(), m = s.size();
        int len = INT_MAX, reti = 0;
        int count = 0;

        for (int left = 0, right = 0; right < m; right++) {
            char in = s[right];
            hash2[in]++;
            
            // 进窗口 + 维护 count
            if (hash1.count(in) && hash2[in] == hash1[in]) {
                count++;
            }
            
            while (count == n) {
                // 更新结果
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    reti = left;
                }
                
                // 出窗口 + 维护 count
                char out = s[left++];
                if (hash1.count(out) && hash2[out] == hash1[out]) {
                    count--;
                }
                hash2[out]--;
            }
        }
        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, begin = -1;
        int count = 0;

        for (int left = 0, right = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++; // 进窗口 + 维护 count
            
            while (count == kinds) { // 判断条件
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--; // 出窗口 + 维护 count
            }
        }
        return begin == -1 ? "" : s.substr(begin, minlen);
    }
};

算法总结

优化版利用定长数组避免了哈希表的开销，在字符集有限时效率更高。核心逻辑依然是维护 count 变量来代表当前窗口满足要求的字符种类数，避免每次循环都遍历整个哈希表。