滑动窗口算法实战：串联所有单词的子串与最小覆盖子串
15. 串联所有单词的子串
题目描述
给定一个字符串 s 和一些长度相同的单词 words，找出 s 中恰好包含 words 中所有单词的串联子串的起始索引。
解法思路
这道题的核心在于将每个单词视为一个整体字符。如果我们将单词看作字母，问题就转化为寻找字符串中所有单词的异位词组合。
主要差异点在于：
- 哈希表存储的是
string到int的映射，用于统计单词频次。 - 窗口的左右指针移动步长固定为单词长度
len。 - 由于起始位置不同可能导致匹配结果不同，外层循环需要遍历
0到len-1作为初始偏移量。
C++ 代码实现
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();
// 外层循环处理不同的起始偏移量
for (int i = 0; i < len; i++) {
unordered_map<string, int> hash2; // 当前窗口内的单词统计
int count = 0; // 窗口中有效单词的个数
int left = i;
// 注意：right + len <= n 防止越界，避免 size_t 与 int 运算时的类型转换问题
( right = i; right + len <= n; right += len) {
string str1 = s.(right, len);
hash2[str1]++;
(hash2[str1] <= hash1[str1]) {
count++;
}
(right - left + > len * m) {
string str2 = s.(left, len);
(hash2[str2] <= hash1[str2]) {
count--;
}
hash2[str2]--;
left += len;
}
(count == m) {
ret.(left);
}
}
}
ret;
}
};
