题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个字符串的数组与一个长字符串。现在定义由字符串数组中每个字符串按任意顺序组成的新字符串为一个子串，求长字符串中，所有子串出现的初始索引。

思路分享

定长滑动窗口的高级变式，首先假设读者已经具备定长滑动窗口的基本知识（【Leetcode Daily】1456定长子串中元音的最大数目），下面模拟一遍陆爻齐从懵逼到 ac 的思路历程。
刚开始下意识地想直接套模板，也就是窗口每次滑入一个字符，然后判断窗口内的单词组成情况。但是这么做的话，其实基本与暴力无异，都是一次遍历获取子串，另一次遍历获取子串内容，违背了滑动窗口对窗口内只用 O（1）复杂度处理的初衷。
既然一个个字母滑入不行，那就试试一个个单词滑入吧，题目中也提示了“ words 中所有字符串长度相同”，换句话就是子串长度固定，且子串中的单词长度也固定。那就把单词当作之前的字母，把子串长度视为窗口大小的限制，这样一写，确实把样例 demo 给过了。当陆爻齐高高兴兴地提交时，遭了当头一棒。
上面的这个方法其实符合了核心思想，但忽略了一点，一次滑动一个单词的距离，不就错过了其中单词长度的情况吗？比如一次划四个字母，那么整个子串可能出现的索引只能是四的倍数，而虽然子串及其中间的单词长度固定，但起始的索引可没固定。这里就要引入多起点滑动窗口了。
所谓的多起点滑动窗口，就是设置多个长度相同的窗口，从不同的起点开始滑动。拿本题来说，如果单词长度为四，那么就需要三个窗口，分别从0，1，2三个起点开始滑，这样才能覆盖到所有的索引情况。不过这个方法如何实现，陆爻齐发现自己的写法与看到的几个题解不太相同，下面都会简单说明一下。
先说说陆爻齐的解法，陆爻齐采用二重循环，因为内层是定长滑动窗口模板，外层则是设置滑动窗口起点。每次外层循环都会重置窗口对应的哈希表以及对于窗口内单词数目的记录。思路很简单，不多做说明。代码也在下面可供参考。
那么主要说说别人题解的实现思路，别人是通过多个哈希表，每个哈希表记录一个窗口对应的单词，所以就不需要对哈希表的清空。相当于用空间复杂度换一点时间，但是大部分情况下还是陆爻齐的解法更优：）（时间上）

代码解答（强烈建议自行解答后再看）

陆爻齐的解法

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> rec_words;
        unordered_map<string, int> rec_win;

        for (const string a : words) {
            rec_words[a]++;
        }

        int word_size = words[0].size();
        int win_size = word_size*words.size();

        vector<int> rec;
        for (int j = 0; j < word_size; j++) {
            //cout << j << endl;
            rec_win.clear();
            int word_count = 0;
            for (int i = word_size+j; i <= s.size(); i+=word_size) {
                string tmp=s.substr(i-word_size, word_size);
                //cout << "enter:" << tmp << endl;
                word_count++;
                rec_win[tmp]++;

                if (word_count < words.size()) {
                    continue;
                }

                if (rec_win == rec_words) {
                    rec.push_back(i-win_size);
                }

                string q_str = s.substr(i-win_size, word_size);
                //cout << "quit:" << q_str << endl;
                if (--rec_win[q_str]==0) {
                    rec_win.erase(q_str);
                }
            }
        }
        return rec;
    }
};