在解析这道题目之前，我们看一个类似的题目：
1. 找到字符串中所有字母异位词
1. 题目描述
题目链接
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
2. 思考
这是一个典型的滑动窗口的题目，在 242. 有效的字母异位词 中，我们使用哈希表来记录字符频率，如何比较两个字符串是否是字母异位词呢？有两种方法：分别记录频率，然后直接比较（C++容器可以用==来逐元素比较）；或者是对两个字符串采用正负步长，对字符串a中出现的字符ch，ch的频率+1，对于b中出现的ch其频率-1，那么最终我们统计频率不为0的字符的个数，如果不为0，则a与b不是字母异位词，否则是。这样做的理由是，对于两个字符串中都未出现的字符或者都出现但出现次数相等的单词，最终频率就会为0，如果两字符串中各字符出现次数相等，那么所有字符的最终频率都为0，也就不会有频率不为0的字符。
对于本题，我们结果242题的方法以及滑动窗口，维护一个大小为p.size()的窗口，统计里面的字符频率，并和p中的字符频率比较，如果相等，那么我们就找到一个p的字母异位词。这里的比较可以采用上述的正负步长方法，先对p中的字符频率统计一次，然后对s中第一个长为p.size()的窗口字符频率统计一次，用正负步长方法比较是否相等，相等则把位置0放入答案（s中第一个窗口的起点）。
int count[26] = {0}, diff = 0, i;
for (i = 0; i < plen; ++i) {
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
for (i = 0; i < 26; ++i) {
if (count[i]) ++diff;
}
if (!diff) ans.emplace_back(0);
上述代码中，diff也就是最终频率不为0的字符的个数，或者也可以说是两字符串存在频率差异的字符的个数，只有这个值为0，两字符串才是字母异位词。在此之后，需要在s中向右滑动窗口，注意这里的窗口大小不变，因此每向右滑动一个位置，最左侧字符被抛弃，最右侧字符进入窗口，此时需要记录两次频率变化，最左侧字符频率-1，最右侧字符频率+1，在这个过程中，要注意字符频率是否变为0或者不再为0，因为如果字符频率由0变成了非0（因为只变化1，因此只会变为1或-1），那么两字符串产生了一个新的差异字符，diff应该+1；反正，由非0变成了0，说明有一个差异字符被消除了，因此diff要-1。然后再检查diff是否为0，如果为0那么当前窗口的起始位置也应该放入答案。重复上述过程直到窗口无法再滑动为止，整体代码如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int slen = s.size(), plen = p.size();
if (slen < plen) return ans;
int count[26] = {0}, diff = 0, i;
// 统计p和s中第一个窗口的字符频率
for (i = 0; i < plen; ++i) {
++count[s[i] - 'a'];
--count[p[i] - 'a'];
}
// 检查差异字符个数diff
for (i = 0; i < 26; ++i) {
if (count[i]) ++diff;
}
// diff为0则窗口起始位置就是答案
if (!diff) ans.emplace_back(0);
int go, come;
// 向右滑动窗口（窗口大小固定）
for (i = 0; i < slen - plen; ++i) {
// 字符go被滑出窗口
go = s[i] - 'a';
--count[go];
// 更新字符频率以及diff
if (count[go] == 0) --diff;
else if (count[go] == -1) ++diff;
// 字符come被滑出窗口
come = s[i + plen] - 'a';
// 更新字符频率以及diff
++count[come];
if (count[come] == 0) --diff;
else if (count[come] == 1) ++diff;
// diff为0则窗口起始位置就是答案
if (!diff) ans.emplace_back(i + 1);
}
return ans;
}
};
3. 额外的思考
这样做其实并不高效（尤其是数据量较大的情况下），因为可能p里面的字符数量并不多（这并不影响p是不是很长），比如p是aaaaaaaaaa，而s中当前窗口是aaaaaaaaba，两者很明显不匹配，按照上述方法窗口应该向右滑动一位，但是实际上我们很明显可以看出，这里向右滑动1位的窗口仍然是和p不匹配的，因为b并没有滑出窗口，而这样的无效滑动至少要重复8次，才能把b滑出窗口，这在p长度非常长的情况下是非常影响性能的。
所以我们需要考虑如何避免这种情况，一种常用的办法是可变滑动窗口，这种窗口大小是不固定的，由一对指针left和right控制左右边界（left ≤ right），可以通过右移right来扩大窗口大小（窗口大小可以通过right - left + 1来计算，当然也可以额外使用一个计数器来存，比较方便）。
那么对于上述存在的问题，我们在扩展窗口的过程中，不断右移right并统计遇到的字符的频率，如果发现right指向了一个未知的字符，也就是p中频率为0（不存在）的字符（这里我们不再使用正负步长，而是分别统计p中字符和窗口内字符的频率），比如aaaaaaaab（此时我们假设窗口还没有扩展到最大）中的b，那么我们不再继续扩展窗口，而是将左右指针都移动到字符b的右边（也就是right + 1的位置），大小置0，重新开始扩展，这样就避免了无效的滑动。
而可变窗口还可以解决一个问题，就是当前窗口right遇到的字符，其窗口内频率如果已经等于p中该字符的频率，再加上当前这一个，一定就大于p中对应的字符频率了（称为超限字符），很明显，它们无法匹配。因此类似于上面那种情况，就不再扩展了，但这里并不需要将窗口整个移到该字符右边，我们只需要左移一位左指针即可，因为只有这种方式可能使得该字符频率不再超限。整体代码如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
vector<int> pmap(26, 0);
vector<int> window(26, 0);
// 统计字符串p的字符频率
for (auto& ch: p) ++pmap[ch - 'a'];
// 初始化左右指针和窗口大小
int left = 0, right = left, count = 0;
int sl = s.size(), nums = p.size(), cur;
// 控制窗口起始位置（左指针）不越界
while (left + nums <= sl) {
// 不断右移右指针，即扩展窗口
while (count < nums) {
cur = s[right] - 'a';
// 遇到未知字符或超限字符，不再扩展窗口
if (!pmap[cur] || window[cur] >= pmap[cur]) break;
++window[cur];
++right; ++count;
}
// 直接比较窗口和p的字符频率，判断窗口与p是否匹配
if (window == pmap) ans.emplace_back(left);
// 如果是遇到未知字符（而退出），那么重置窗口到该字符右边
if (!pmap[cur]) {
++right;
left = right;
count = 0;
fill(window.begin(), window.end(), 0);
// 否则窗口可能正常扩展完，也可能遇到超限字符
// 不论哪种情况，左指针右移，窗口收缩
} else {
--window[s[left] - 'a'];
++left;
--count;
}
}
return ans;
}
};
正题来了：
2. 串联所有单词的子串
1. 题目描述
题目链接
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。
2. 思考
乍一看好像很复杂，但其实本质上和上一题是一样的，因为题目已经限定words里面的每个单词长度相等，把一个单词想象成一个字符，那么找words的串联子串，不就相当于找words的字母异位词吗？（各个单词数量均相等，只是顺序不同）。那么这道题同样可以用滑动窗口来做，只不过滑动的距离由1个位置（字符）变成了一个单词长度，而且由于单词是没有范围的（不像上题规定字符都是小写字母），因此不能用数组偷懒，而是必须使用哈希表。
和上题优化方法一样的思想，采用可变滑动窗口，不过这里要注意一点，由于滑动窗口一次滑动一个单词的距离，因此滑动窗口的起点是有多个的（不像之前一次滑动1个字符），比如单词长度为3，那么起点0的窗口只能滑动到3 6，起点1的窗口只能滑动到4 7，起点为2的窗口只能滑动到5 8，它们的范围是互不重叠的。因此需要在最外面套一层循环，代表不同的窗口（最左）起始点，每个起点不同的窗口都需要独立的左右指针、窗口大小计数器，以及一个独立的单词频率统计表。
3. 代码实现
对上题代码略作修改，最终代码如下：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int nums = words.size(), len = words[0].size(), sl = s.size();
int total = nums * len;
unordered_map<string, int> map;
vector<int> ans;
// 单词表频率只计算一次
for (auto& word: words) ++map[word];
// 对于不同的窗口起始点
for (int i = 0; i < len; ++i) {
// 窗口的左指针、右指针以及单词数量
int left = i, right = left, count = 0;
unordered_map<string, int> window;
// 防止左指针越界
while (left + total <= sl) {
string tmp;
// 不断右移右指针以扩展窗口
while (count < nums) {
// 获取右指针指向的单词
tmp = s.substr(right, len);
// 如遇到未知单词或者过多单词，退出，不再扩展
if (!map.count(tmp) || window[tmp] >= map[tmp]) break;
++window[tmp];
right += len;
++count;
}
// 比较当前窗口单词频率与单词表
if (window == map) ans.emplace_back(left);
// 如果因为未知单词而退出，应该重置窗口，从未知单词右边开始
if (!map.count(tmp)) {
right += len;
left = right;
count = 0;
window.clear();
// 否则无论是窗口正常结束还是因过多单词而异常退出，
// 都只将窗口左指针右移一个单词位置
} else {
--count;
--window[s.substr(left, len)];
left += len;
}
}
}
return ans;
}
};