没有什么是不可能的 ; 这个词本意就是“我有一切可能” 。

题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

解题代码：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(words.empty()) return {};
        unordered_map<string,int> wordmap,smap;
        for(string word:words) wordmap[word]++;
        int wordlen = words[0].size();
        int wordnum = words.size();
        vector<int> ans;
        for(int k=0;k<wordlen;k++){
            int i=k,j=k;
            while(i<s.size()-wordnum*wordlen+1){
                while(j<i+wordnum*wordlen){
                    string temp = s.substr(j,wordlen);
                    smap[temp]++;
                    j+=wordlen;
                    if(wordmap[temp]==0){//情况二，有words中不存在的单词
                        i=j;//对i加速
                        smap.clear();
                        break;
                    }
                    else if(smap[temp]>wordmap[temp]){//情况三，子串中temp数量超了
                        while(smap[temp]>wordmap[temp]){
                            smap[s.substr(i,wordlen)]--;
                            i+=wordlen;//对i加速
                        }
                        break;
                    }                   
                }
                //正确匹配，由于情况二和三都对i加速了，不可能满足此条件
                if(j==i+wordlen*wordnum){
                    ans.push_back(i);
                    smap[s.substr(i,wordlen)]--;
                    i+=wordlen;//i正常前进
                }
            }
            smap.clear();
        }
        return ans;
    }
};

解读与收获：

困难题。花了我比较长的时间（题解也看了很久），简单说一下思路：用两个hashmap（wordmap,smap）分别用来存放words中的单词和出现数量，以及在窗口中的单词以及出现数量。然后三层循环：第一层是用来确定滑动窗口的出发点，来保证能遍历到s的每一个子串，第二、三层循环用来进行窗口滑动，i是窗口左边界，j为右边界。每次取右边界的一个长为wordlen的单词进行判断，如果该单词不在wordmap，则将i加速到j的位置（之前窗口内所有单词都失效了），还有可能是单词在wordmap但是数量超过了规定数，则i进行右移（将一个单词移出窗口），若两种情况都不符合，说明是我们要找的字串，记录下标i。