# LeetCode 30\. 串联所有单词的子串 题解（滑动窗口 \+ 哈希表）
## 一、题目描述
给定一个字符串 `s` 和一个长度全部相同的字符串数组 `words`。
**串联子串定义**：由 `words` 中所有单词**不重复、任意顺序**拼接组成的连续子串。
要求：返回 `s` 中所有串联子串的**起始下标**，答案顺序不限。
### 关键已知条件
- `words` 中**所有单词长度完全一致**（本题核心突破口）；
- 串联子串长度固定 = 单词个数 × 单个单词长度；
- 子串必须包含 **全部单词各一次**，不能多、不能少、不能重复缺失。
## 二、解题难点与思路分析
### 1\. 暴力解法缺陷
枚举 `s` 中所有等长区间，截取子串拆分比对单词哈希表，时间复杂度极高，会超时，无法通过大数据样例。
### 2\. 最优算法：偏移分组 \+ 滑动窗口 \+ 哈希表
利用 **所有单词长度相同** 这一特性，进行算法优化：
1. **偏移分组**：假设单词长度为 `len`，字符串匹配的起始偏移只会有 `0 ~ len-1` 共 `len` 种情况。
例如单词长度为2，匹配起点只会是偶数偏移或奇数偏移，无需逐个字符遍历。
2. **固定步长滑动窗口**：每组偏移下，以 `len` 为步长，每次截取一个单词长度的子串，模拟单词滑动。
3. **双哈希表计数**：`need` 存储标准单词频次，`have` 存储当前窗口内单词频次。
4. **合法窗口判定**：窗口内匹配单词总数等于 `words` 总个数时，记录起始下标。
### 3\. 核心原理
- 总匹配子串长度固定：`total = 单词数 × 单单词长度`；
- 不合法单词直接重置窗口，超量单词从左边界收缩窗口；
- 匹配成功后窗口右移一位（步长len），继续寻找后续合法解。
## 三、完整AC代码（C\+\+）
```cpp
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> result;
// 特判：空串直接返回
if (s.empty() || words.empty()) return result;
const int n = words.size(); // 单词总个数
const int len = words[0].size(); // 单个单词长度
const int total = n * len; // 合法子串总长度
// 原串长度不足，直接无解
if (s.size() < static_cast<size_t>(total)) return result;
// 构建目标单词频次表
unordered_map<string, int> need;
for (const auto& w : words) need[w]++;
// 枚举所有偏移分组：0 ~ len-1
for (int offset = 0; offset < len; ++offset) {
unordered_map<string, int> have; // 当前窗口单词频次
int count = 0; // 窗口内匹配成功的单词数
int left = offset; // 窗口左边界
// 以 len 为步长滑动窗口
for (int i = offset; i + len <= (int)s.size(); i += len) {
string w = s.substr(i, len);
// 情况1：出现不存在的单词，窗口直接作废重置
if (!need.count(w)) {
have.clear();
count = 0;
left = i + len;
continue;
}
// 统计当前窗口单词数量
have[w]++;
// 未超出需求，匹配数+1
if (have[w] <= need[w]) {
count++;
} else {
// 情况2：当前单词数量超标，收缩左窗口，直到合法
while (have[w] > need[w]) {
string out_w = s.substr(left, len);
have[out_w]--;
if (have[out_w] < need[out_w]) count--;
left += len;
}
}
// 窗口完全匹配，记录答案
if (count == n) {
result.push_back(left);
// 滑动窗口，左边界右移，寻找下一组解
string out_w = s.substr(left, len);
have[out_w]--;
count--;
left += len;
}
}
}
return result;
}
};
四、代码逐行详细解析
1. 基础特判与变量定义
-
判断字符串或单词数组为空，直接返回空结果；
-
n：单词个数，len：单个单词长度，total：合法串联子串固定总长度； -
若原字符串长度小于
total，不可能存在解，直接返回。
2. 构建标准单词频次表 need
遍历 words 数组，统计每个单词出现次数，作为窗口匹配的标准答案。
3. 偏移分组遍历（核心优化点）
循环 offset 0 ~ len-1：
所有合法的单词起始位置，必然属于这 len 种偏移情况之一，避免重复无效遍历。
4. 每组偏移内滑动窗口
-
have：记录当前窗口内单词频次； -
count：记录当前窗口完全匹配的单词数量； -
left：滑动窗口左边界。
以 len 为步长遍历字符串，每次截取一个完整单词长度的子串。
5. 窗口三大更新逻辑
情况一：出现非法单词（不在words中）
当前窗口彻底失效，清空频次表、匹配计数，左边界直接跳到当前单词下一位。
情况二：当前单词数量合法
窗口内单词计数累加，未超标准数量则匹配成功数+1。
情况三：当前单词数量超标
不断右移左边界，移除最左侧单词，更新频次和匹配数，直到当前单词数量合法。
6. 匹配成功记录答案
当 count == n，说明当前窗口包含所有单词且数量匹配，记录左边界为答案起点。
随后收缩窗口，继续向后匹配新的合法子串。
五、复杂度分析
时间复杂度：O(len × N)
len 为单词长度，N 为字符串 s 长度。共 len 组偏移遍历，每组线性遍历字符串，每个字符仅处理一次，效率极高。
空间复杂度：O(M)
M 为单词数组的不同单词数量，仅使用两个哈希表存储单词频次。
<br/>