【LeetCode30_滑动窗口 + 哈希表】：三招搞定“串联所有单词的子串”

引言

对于初学编程的小伙伴来说，LeetCode 中的字符串匹配类题目常常让人头疼 —— 既要处理复杂的字符组合，又要兼顾效率，很容易陷入 “暴力破解超时” 的困境。

今天要讲的第 30 题 “串联所有单词的子串”，就是一道典型的 “看似复杂但有巧解” 的题目。它不仅考察对字符串的基本操作，还能帮我们入门 “哈希表” 和 “滑动窗口” 这两个编程中超实用的技巧。这两个技巧就像两把钥匙，能打开很多字符串、数组类题目的大门，学会后会发现很多难题都能迎刃而解。接下来，我们就从题目理解开始，一步步拆解思路，逐行分析代码，让新手也能轻松掌握这道题的解法！

目录

一、题目理解：到底要找什么？

先把复杂题目变简单！题目说：

• 给一个字符串s和一个单词数组words，数组里所有单词长度都一样
• 我们要找s中这样的子串：它刚好是words里所有单词随便排序后拼接起来的
• 最后返回这些子串的开始索引（顺序无所谓）

举个例子就明白：
如果words = ["foo","bar"]，那拼接后的可能是"barfoo"或"foobar"，只要s里有这两个子串，它们的起始位置就要返回。

关键规律：

• 每个单词长度是len，words有m个单词，所以目标子串长度一定是len * m（比如上面的3*2=6）
• 只要子串长度不对，直接排除，不用浪费时间判断

二、核心思路：哈希表+滑动窗口

这道题的核心是用「哈希表记频次」+「滑动窗口找符合条件的子串」，新手可以这么理解：

1. 哈希表就像一个计数器：先记下words里每个单词出现了几次（比如["foo","bar"]就是foo:1，bar:1）
2. 滑动窗口就像一个可移动的“框”：在s里框出一段长度为len*m的子串，看看这个框里的单词是不是刚好和words里的单词完全匹配（数量和种类都一致）
   

为什么要这么做？

• 如果暴力遍历所有可能的子串，再拆分单词对比，会特别慢（比如s很长、words很多的时候）
• 哈希表查频次很快，滑动窗口能重复利用之前的判断结果，效率大大提高

三、代码逐行拆解：新手也能看明白

先看完整代码（已加详细注释）：

classSolution{public:vector<int>findSubstring(string s,vector<string>&words){// 哈希表1：记录words中所有单词的频次（比如["foo","bar"]就是foo:1，bar:1）unordered_map<string,int>hash1;for(auto&word:words)hash1[word]++;// 遍历words，给每个单词计数vector<int>ret;// 用来存最终找到的起始索引intlen=words[0].size();// 每个单词的长度（题目说所有单词长度相同）intm=words.size();// words数组的单词个数inttotal_len=len*m;// 目标子串的总长度（必须是这个长度才有可能符合条件）// 关键循环1：按单词长度分轮遍历（比如单词长3，就分0、1、2三个起始位置开始）for(inti=0;i<len;i++){unordered_map<string,int>hash2;// 哈希表2：记录当前窗口里的单词频次// 滑动窗口的三个关键变量：left（窗口左边界）、right（窗口右边界）、count（匹配上的单词个数）for(intleft=i,right=i,count=0;right+len<=s.size();right+=len){// 1. 把当前right位置的单词加入窗口（进窗口）string in_word=s.substr(right,len);// 从right开始，取len个字符作为当前单词hash2[in_word]++;// 给这个单词的频次+1// 2. 维护count：如果当前单词在words里，且窗口里的频次没超过words里的频次，说明匹配上一个if(hash2[in_word]<=hash1[in_word]){count++;}// 3. 窗口长度超过目标长度了，需要把左边的单词移出窗口（出窗口）if(right-left+1>total_len){string out_word=s.substr(left,len);// 要移出的左边单词// 如果移出的单词是words里的，且移出前的频次没超过words里的频次，说明匹配数要减1if(hash2[out_word]<=hash1[out_word]){count--;}hash2[out_word]--;// 移出单词，频次-1left+=len;// 左边界右移，窗口缩小}// 4. 如果匹配上的单词个数等于words的长度，说明当前窗口是符合条件的子串if(count==m){ret.push_back(left);// 记录左边界（起始索引）}}}returnret;// 返回所有找到的起始索引}};

关键部分详细解释

1. 两个哈希表的作用

• hash1：全局计数器，记录words中每个单词必须出现的次数（比如words = ["bar","foo","the"]，就是bar:1、foo:1、the:1）
• hash2：窗口计数器，记录当前滑动窗口中每个单词出现的次数（比如窗口里是"foo",“bar”,“the”，就是foo:1、bar:1、the:1）

2. 为什么要分len轮遍历？

比如单词长度是3（len=3），我们要考虑三种起始位置：

• 第0轮：从索引0、3、6…开始取单词（0→3→6→…）
• 第1轮：从索引1、4、7…开始取单词（1→4→7→…）
• 第2轮：从索引2、5、8…开始取单词（2→5→8→…）
  

这样做是为了不遗漏任何可能的子串！因为目标子串是由完整单词拼接的，所以起始位置一定是这len种情况之一。

3. 滑动窗口的核心操作（进窗口→出窗口→判断）

• 进窗口：把右边的单词加入hash2，如果这个单词是words里的，且没超量，就给匹配数count+1
• 出窗口：如果窗口太长（超过total_len），就把左边的单词移出hash2，如果这个单词是words里的，且移出前没超量，就给count-1
• 判断：如果count == m（匹配数等于words的单词个数），说明当前窗口刚好是符合条件的子串，记录左边界

四、新手容易踩的坑&解决办法

1. 忘记单词长度相同的条件：题目明确说words中所有字符串长度相同，所以可以直接用words[0].size()，不用考虑每个单词长度不一样的情况
2. 窗口长度计算错误：窗口长度是right - left + 1，目标长度是len * m，当窗口超过这个长度时必须移出左边的单词
3. count的维护逻辑：只有当单词在words里，且频次没超量时，才增减count，否则不管（比如s里的单词不在words里，加入或移出都不影响count）
4. 哈希表的使用：unordered_map的键是字符串（单词），值是频次，新手要注意substr的用法（substr(起始索引, 长度)）

五、例子演示（帮助理解）

以示例1为例：

• s = "barfoothefoobarman"，words = ["foo","bar"]
• len=3，m=2，total_len=6
• 第0轮遍历（i=0）：
  • left=0，right=0：进窗口"bar"，hash2["bar"]=1，count=1（因为hash1["bar"]=1）
  • right=3：进窗口"foo"，hash2["foo"]=1，count=2，此时count == m，记录left=0（第一个答案）
  • right=6：进窗口"the"，窗口长度=7>6，移出左边"bar"，hash2["bar"]=0，count=1
  • … 继续滑动，直到right=9：
  • right=9：进窗口"foo"，hash2["foo"]=1，count=1
  • right=12：进窗口"bar"，hash2["bar"]=1，count=2，记录left=9（第二个答案）

最终返回[0,9]，和示例结果一致！

六、总结：解题步骤（新手可直接套用）

1. 计算单词长度len、单词个数m、目标子串长度total_len = len * m
2. 用hash1记录words中每个单词的频次
3. 按len轮遍历（起始位置0到len-1）：
   • 初始化窗口变量（left、right、count）和hash2
   • 滑动窗口：每次右移len个位置（取一个完整单词）
   • 进窗口：更新hash2和count
   • 出窗口：如果窗口超长，更新hash2和count
   • 判断：如果count == m，记录left
4. 返回所有记录的起始索引

这种方法的效率很高，适合处理题目中的数据规模（s长度<=1e4，words长度<=5000），新手掌握后，遇到类似的字符串匹配问题都可以用「哈希表+滑动窗口」的思路来解决！