题目

链接：leetcode链接

思路分析（滑动窗口）

这道题目类似寻找异位词的题目，我认为是寻找异位词的升级版
传送门:寻找异位词

为什么说像呢？
注意：这道题目中words数组里面的字符串长度都是相同的，不妨令长度为len

我们这么来看这道题目，我们把words数组里面的字符串都看成一个字母，那这个题目不就是让我们去在s字符串中去寻找words数组的异位词吗？

难点在哪里呢？

我们以示例一为例：
s = “barfoothefoobarman”, words = [“foo”,“bar”]
在s中寻找的时候，可能bar一组，也可能arf一组，也可能rfo一组，情况非常多
但是，不要忘记了，words数组里面的字符串长度是相同的，
也就是说s中一共也就只有len中情况，直接走len次滑动窗口就行了。

设置count来统计有效元素
我们只需要去统计滑动窗口中有效元素的个数即可。
依旧是进窗口后维护count，
出窗口前维护count。

当count==words.size(），此时的left即为有效下标。

注意：

该题目为定长滑动窗口，当窗口长度 > word.size()就要出窗口了。
该题目需要走len次滑动窗口

代码

vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;unordered_map<string,int> hash2;vector<int> v;for(auto& s1:words) hash1[s1]++;int count = 0,len = words[0].size(),size = words.size();for(int i = 0;i < len;++i)//走len次滑动窗口{ hash2.clear();//新的一次滑动窗口要重新初始化一下count = 0;for(int left = i,right = i;right < s.size();right += len){string in = s.substr(right,len);hash2[in]++;//进窗口if(hash1.count(in)&&hash2[in] <= hash1[in]) count++;if((right - left) / len + 1 > size)//出窗口{string out = s.substr(left,len);if(hash1.count(out) && hash2[out] <= hash1[out]) count--;hash2[out]--;left+= len;}if(count == size) v.push_back(left);}}return v;}