https://blog.csdn.net/2601_95366422/article/details/158618804
上节课链接
一.题目
30. 串联所有单词的子串 – 力扣(LeetCode)

二.思路
2.1 审题
这道题要求在一个字符串 s 中找出所有 串联子串 的起始索引。所谓 串联子串,是指由 words 数组中的 所有字符串 以 任意顺序 连接而成,并且每个单词 恰好使用一次 的子串。题目给出的关键条件是 words 中所有单词 长度相同,因此每个可能的串联子串的长度也是 固定的,即 单词个数 × 单个单词长度。这道题的思路与 找到字符串中所有字母异位词 类似,只是将比较的单位从 单个字符 换成了 等长的单词。最终需要返回所有满足条件的子串在 s 中的开始索引,返回顺序 不限。
2.2 思路讲解
这道题虽然与上一题“找到字符串中所有字母的异位词”思路相似,但难度提升为困难,主要是因为比较的单位从单个字符变成了等长的单词,带来了几个关键的升级点。
升级点一:哈希表的容器化
上一题中,字符范围有限(小写字母),我们可以用固定数组模拟哈希表。而本题的单词是字符串,数量未知,因此必须使用真正的哈希表容器(如 unordered_map)来记录 words 中每个单词的出现次数,以及当前窗口内单词的出现次数。
升级点二:滑动窗口的移动步长
由于每个单词长度相同(记为 len),窗口的扩展和收缩不再是以字符为单位,而是以单词为单位。即每次右指针移动 len 步,取出一个单词加入窗口;左指针也移动 len 步,移出一个单词。这相当于把字符串 s 按单词长度切分成了多个“单词块”,然后在这些块上进行滑动窗口。
升级点三:多种起始偏移
因为单词长度可能大于1,所以滑动窗口的起始位置并不是只有 0 一种。例如,如果单词长度为3,那么从下标 0、1、2 开始,分别对应三种不同的“单词划分”方式(如图例所示)。因此,我们需要对每一种可能的起始偏移 i(从 0 到 len-1)都进行一次滑动窗口遍历,这样才能覆盖所有可能的子串。
细节处理
-
在每次滑动窗口过程中,维护一个哈希表记录窗口内单词的出现次数,同时用一个计数器记录当前已匹配的单词个数。
-
当窗口内单词个数超过 words 的长度时,需要从左边移出单词,并更新哈希表和计数器。
-
当计数器等于 words 的长度时,说明找到一个有效起始索引。
理解了这些升级点,这道题就不再那么困难了。
三.代码演示
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> v;
unordered_map<string,int>hash1;
for(const auto& i : words)
{
hash1[i]++;
}
int n = s.size();
int len = words[0].size();//单词长度
int m = words.size();
for(int i = 0; i < len;i++)
{
unordered_map<string,int>hash2;
for(int left = i,right = i,count = 0;right + len <= n;right += len)
{
//进窗口
string out1 = s.substr(right,len);//元素字符串
hash2[out1]++;
if(hash2[out1] <= hash1[out1])
count++;
//判断条件
if(right – left + 1 > len * m)
{
string out2 = s.substr(left,len);//元素字符串
if(hash2[out2] <= hash1[out2])
count–;
//出窗口
hash2[out2]–;
left += len;
}
//更新结果
if(count == m)
v.push_back(left);
}
}
return v;
}
};
四.代码讲解
第一步:初始化哈希表和变量
-
定义一个哈希表 hash1(unordered_map<string, int>),遍历 words 数组,统计每个单词出现的次数,作为目标词频。
-
获取字符串 s 的长度 n,单词长度 len = words[0].size(),单词个数 m = words.size()。
-
准备结果数组 v。
第二步:外层循环——处理不同的起始偏移
由于单词长度可能大于1,滑动窗口的起始位置不能只从0开始,而需要从 0 到 len-1 每个偏移都尝试一次,这样才能覆盖所有可能的单词划分。
-
循环 i 从 0 到 len-1,对于每个偏移 i,执行内层滑动窗口。
第三步:内层滑动窗口初始化
对于当前偏移 i:
-
定义一个新的哈希表 hash2,用于记录当前窗口内单词的出现次数。
-
初始化左指针 left = i,右指针 right = i,计数器 count = 0(记录当前窗口内有效匹配的单词个数,即属于 words 且数量未超出的单词数)。
第四步:遍历字符串,移动右指针(进窗口)
使用 for 循环,条件为 right + len <= n(确保能取出完整单词),每次右移 len 步:
-
从 s 中取出以 right 开头、长度为 len 的子串 out1 = s.substr(right, len)。
-
将该单词加入 hash2:hash2[out1]++。
-
维护 count:如果加入后该单词在 hash2 中的数量 ≤ 它在 hash1 中的数量,说明这个单词是有效匹配的一部分,count++。
第五步:维护窗口大小(出窗口)
窗口内单词个数为 (right – left)/len + 1。当窗口大小超过 m 个单词时(即 right – left + 1 > len * m),需要移出最左边的单词:
-
取出左指针指向的单词 out2 = s.substr(left, len)。
-
如果移出前该单词在 hash2 中的数量 ≤ hash1 中的数量(说明它是一个有效匹配),则 count–。
-
然后将 hash2[out2]–,即从窗口中移除该单词。
-
左指针右移 len 步:left += len。
第六步:更新结果
每次完成右移和可能的出窗口后,检查当前 count 是否等于 m。如果相等,说明窗口内恰好包含了 words 中的所有单词(每个单词次数也匹配),此时左指针 left 就是当前有效子串的起始索引,将其加入结果数组 v。
第七步:继续循环
内层 for 循环继续右移 right,直到遍历完当前偏移下的所有可能位置。然后外层切换到下一个偏移 i,重复上述过程。
第八步:返回结果
所有偏移处理完毕后,返回结果数组 v。
重点总结
-
核心思路是将字符异位词问题扩展为单词异位词问题,利用滑动窗口 + 哈希表。
-
由于单词等长,窗口每次移动 len 步,并需要考虑 len 种起始偏移。
-
计数器 count 实时维护窗口内有效匹配的单词个数,避免每次比较整个哈希表,是优化关键。
-
进出窗口时对 count 的更新逻辑与上一题完全一致,只是单位从字符换成了单词。

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)

