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

15. 串联所有单词的子串

题目描述

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

示例

输入： s = "barfoothefoobarman" words = ["foo", "bar"] 输出：[0, 9] 解释：从索引 0 开始是 "barfoo"，从索引 9 开始是 "foobar"。

解题思路

这道题的核心在于将'单词'视为整体单位进行滑动窗口处理。如果我们将每个单词看作一个字符，问题就转化为了寻找字符串中的异位词组合。

关键差异点：

• 哈希表的键类型变为 string，用于统计单词频次。
• 左右指针的移动步长不再是 1，而是单词的长度 len。
• 由于起始位置可能落在单词中间，我们需要对 0 到 len-1 分别作为起点进行多次遍历。

代码实现

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 统计 words 中所有单词出现的频次
        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 <= n 防止越界，避免 size_t 与 int 运算导致的负数陷阱
            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;
    }
};

流程解析

---

16. 最小覆盖子串

题目描述

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

示例

输入： s = "ADOBECODEBANC" t = "ABC" 输出："BANC"

解题思路

这是滑动窗口的经典应用。我们需要维护一个动态窗口，使其包含 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++) {
            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++;
            }
        }
        
        return (begin != -1) ? s.substr(begin, min_len) : "";
    }
};

流程解析

---

这两道题虽然场景不同，但本质都是利用滑动窗口配合频率统计来平衡时间复杂度。关键在于理解如何定义'窗口结束'以及何时移动左指针，掌握这两个模式后，类似的字符串匹配问题就能迎刃而解。