1.題目

題目分析：

有一個字符串s和字符串數組，如何字符串數組里面的元素可以組成一個字符串，然后要在字符串里面找到連續子串跟組成的字符串一樣，返回起始地址。

2.算法原理

這道題可以把字符串數組的元素string看出char，把字符串里面也按照大小合成一個字母，也就是說n個字母組成的單詞在字符串里面找連續子串，就可以用異位詞的方法處理，用哈希表來存儲，string表示字符，int表示出現的次數，先把字符串數組的元素放到哈希表，然后開始進窗口，用substr函數把多個字符一起讀取，放入第二個哈希表中，比較是否大于第一個哈希表這個字符出現的次數，小于說明是第一次出現就可以把count++，當界限大于字符串數組元素總長時，就要開始出窗口了，向判斷次數在--，避免把種類減少了。

注意，上面的情況是按照從開頭開始切分，但有時不是開頭，而是第二個第三個，前面都是無效字符，所以就需要在來一次for循環，次數是字符串數組的單個元素的大小，這樣就可以遍歷所有情況了。

3.代碼實現

優化操作，hash1[in]和hash2[out]有可能會插入新元素，因為都是未出現的，就會開辟空間去存放新元素，造成空間損耗。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> result;unordered_map<string,int> hash1;//unordered_map<string,int> hash2;for(auto& s:words) hash1[s]++;int len=words[0].size(),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<=s.size();right+=len){string in =s.substr(right,len);hash2[in]++;if(hash1.count(in)&&hash2[in]<=hash1[in]) count++;if(right-left+1>len*m){string out=s.substr(left,len);if(hash1.count(out)&&hash2[out]<=hash1[out]){count--;}hash2[out]--;left+=len;}if(count==m) result.push_back(left);}}return result;}
};