1.题目解析

本题的题目要求给出一个字符串 s 与一个字符数组 words ，并且 words 中的所有单词长度均相同，我们要寻找出 s 中是否存在子串符合 words 中单词的任意组合而成，注意重要的一点是 words 中的所有单词的长度均相同，这是解决问题的重要一点

2.算法原理

这里我们要把握的一个点就是words中的所有单词均是长度相同的单词，根据我们上一道题438.找到字符串中所有字符异位词 ，与这道题的思路大同小异，不过本题将元素变成了独立的每个单词，这时我们可以使用"滑动窗口"，将left与right初始均指向s的开头，然后right一次性移动的长度是words中每个单词的长度，并且进行该操作的次数同样是单词的长度，然后使用哈希表来统计窗口与字符串数组中的单词个数，记录窗口内有效元素的个数，在进窗口后检查有效元素的个数，同样出窗口也要检查，最终判断有效个数是否为字符串数组中的单词个数，如果是就直接返回left对应的下标，反之继续进入循环遍历，最终返回数组即可

 

3.代码展示

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;//保存 words 中的单词数目int len = words[0].size();//保存 words 中单词长度int m = words.size();//保存 words 中单词个数for(auto& s : words){ hash1[s]++;}for(int i = 0;i < len;i++){unordered_map<string,int> hash2;for(int left = i,right = i,count = 0;right + len <= s.size();right += len){//进窗口 + 维护 countstring in = s.substr(right,len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]){count++;}//判断if(right - left + 1 > len * m){//出窗口 + 维护 countstring out = s.substr(left,len);if(hash1.count(out) && hash2[out] <= hash1[out]){count--;}hash2[out]--;left += len;}//更新结果if(count == m){ret.push_back(left);}}}return ret;}
};