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;

    }
};