image.png
算是滑动窗口的一道题目吧，此题我们使用2个hashmap，第一个hashmap来记录words中的每个单词出现的个数，然后利用双指针，左指针i和右指针j，右指针一共移动word的长度的次数，然后每次判断len长度的子字符串是否存在于map1中，不是就跳出；当遍历到末尾的时候表示这段窗口就是我们要找的答案，记录左指针的index即可。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if (s.empty() || words.empty()) return ans;
unordered_map<string, int> map1;
for (auto word : words) ++map1[word];
int n = s.size(), num = words.size(), len = words[0].size();
for (int i = 0; i <= n - num * len; i++) {
unordered_map<string, int> map2;
int j = 0;
for (; j < num; j++) {
string str = s.substr(i + j * len, len);
if (map1.find(str) == map1.end()) break;
++map2[str];
if (map2[str] > map1[str]) break;
}
if (j == num) ans.push_back(i);
}
return ans;
}
};
