前言：

上篇我们介绍了滑动窗口的进阶练习，本篇难度继续升级，同样结合具体题目，帮助大家进一步掌握和运用滑动窗口。 

一. 找到字符串中所有字母异位词

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode） 

题目分析：

题目要求返回所有异位词的起始索引，我们首先来了解什么是异位词和起始索引。

异位词：

1. 观察其示例可知，两个字符串的长度和所含字母相同

2. 字母的排列顺序不同

起始索引：该异位词的首字母在原先的字符串中的下标。

思路讲解：

首先可以考虑使用哈希表进行字符串的匹配问题:

字符匹配：

1. 首先用hash2对字符串p中的字符进行一一存储映射

2. 对s中将要匹配的字符串同样进行哈希映射处理

3. 如果两个哈希表完全相同，则该哈希表存储的字符串即为一个异位词 

不难发现，在向后遍历进行存储时，为一个连续的区间，因此同样可尝试使用滑动窗口解决。

滑动窗口：

1. 定义都为0的left和right，right向后遍历的同时进行哈希映射存储，即为进窗口操作。 

2. 当窗口长度大于字符串p的长度时，此处绝对不可能为异位词，因此需要left向后遍历的同时更改哈希映射存储，即为出窗口操作。

3. 当窗口长度与p的长度相等时，即可进行上面提到的字符匹配操作，如果成功匹配，则在vector数组ret中尾插中left的索引，反之则继续进行滑动窗口操作。

算法优化： 

问题：每次字符匹配时，都需要进行26次的判断操作，虽然次数不算多，但在字符串长度较大时，仍会造成较大的时间损耗，那么我们该如何进行优化呢？

解答：大量时间损耗产生的原因是因为冗余的字符匹配，我们可以通过字符计数的方式进行匹配。

1. 异位词的基本要求就是长度相等，另外还需要出现的所有字母次数相同。

2. 我们可以把字符串p的长度记录为m，窗口内有效字母数记为count。

3. 入窗口时的哈希映射记录为in,当入窗口操作时，如果hash1[in]<=hash2[in]，说明进入了一个有效字母，count++。

4. 出窗口时的哈希映射记录为out，当出窗口操作时，如果hash2[out]<=hash2[out]，说明失去了一个有效字母,count--。

5. 当count与m相等时，代表两个字符串的有效字母也相等，此时一定为异位词，直接在vector数组ret中尾插left的索引即可。

代码实现：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int hash2[26]={0};//模拟哈希匹配字符串pint hash1[26]={0};//模拟哈希表记录窗口内的元素情况int m=p.size();//记录p的长度vector<int> ret;for(auto e:p){hash2[e-'a']++;}//存储p中字母出现的次数for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];//进窗口的元素if(++hash1[in-'a']<=hash2[in-'a']){count++;}//进窗口同时维护countif(right-left+1>m){char out=s[left++];if(hash1[out-'a']--<=hash2[out-'a']){count--;}}//出窗口的同时维护countif(count==m){ret.push_back(left);}}return ret;}
};

 注意：

该代码在进行进出窗口操作时，进行了小优化，即在if操作时，既进行了哈希表存储映射的更新，又维护了count。

二. 串联所有单词的子串

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode） 

题目分析：

1. 题目中，words是一个字符数组，且每个元素的长度相同 

2. 要求返回字符串s内的所有串联子串的起始索引。

起始索引在上题中我们已经谈到，因此我们先来了解一下什么是串联子串。

1. 串联子串与words内所有元素相同，且长度即为字符数组的长度。

2. 串联子串中字母的排列顺序与字符数组内元素的排列顺序不同。

不难发现，其实串联子串就是进阶版的异位词。 

算法讲解: 

思路与上题相同，我们只需要把words内的每个元素看作是上题的一个字母即可。

1. 首先利用哈希表存储words内的元素，len表示单个单词的长度，m表示words内的元素个数

2.  与上题中right每次移动一个字母不同，这次right每次需要移动len个长度，并且循环终止条件为right+len<=s.size()，如果不取等于，那么最后一组数据会无法遍历完全。

3. 同时，外层需要嵌套一层执行次数为len次的for循环，表示以第一个单词的各个位置作为进出窗口的起始位置进行遍历。

4. 进出窗口与代码优化维护count操作与上类似。

代码实现：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash2;//利用哈希表映射wordsvector<int> ret;for(auto e:words){hash2[e]++;}int len=words[0].size(),m=words.size();//分别记录单个单词的长度和单词个数for(int i=0;i<len;i++)//执行len次{unordered_map<string,int> hash1;//for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);//剪切出需要进窗口的子串hash1[in]++;if(hash1.count(in)&&hash1[in]<=hash2[in]){count++;}//进窗口同时维护countif(right-left+1>len*m){string out=s.substr(left,len);//剪切出需要出窗口的子串if(hash1.count(out)&&hash1[out]<=hash2[out]){count--;}hash1[out]--;left+=len;}//出窗口同时维护countif(count==m){ret.push_back(left);}}}return ret;}
};

 三. 最小覆盖子串

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题目分析：

题目给出两个字符串s和t，要求求出s内的最小覆盖子串，若不存在，则返回空。

我们首先来了解一下覆盖子串的定义：

1. 由示例不难看出，覆盖字串至少需要涵盖t内的所有字母

2. 覆盖子串内的字母顺序不做要求

3. 易得覆盖字串即为第一题异位词的扩大版

注意：字符串内的字母可能为大写也可能为小写！！！ 

思路讲解：

研究对象是连续的区间，因此可以尝试使⽤滑动窗⼝的思想来解决。
如何判断当前窗⼝内的所有字符是符合要求的呢？

我们可以使⽤两个哈希表，其中⼀个将⽬标串的信息统计起来，另⼀个哈希表动态的维护窗口内字符串的信息。
当动态哈希表中包含⽬标串中所有的字符，并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数，那么当前的窗⼝就是⼀种可⾏的⽅案。

具体过程如下：

定义两个全局的哈希表：

1 号哈希表 hash1 ⽤来记录⼦串的信息， 2 号哈希表 hash2
⽤来记录⽬标串 t 的信息；
b. 实现⼀个接⼝函数，判断当前窗⼝是否满⾜要求：
i. 遍历两个哈希表中对应位置的元素：
• 如果 t 中某个字符的数量⼤于窗⼝中字符的数量，也就是 2 号哈希表某个位置⼤于
1 号哈希表。说明不匹配，返回 false ；
• 如果全都匹配，返回 true 。
主函数中：
a. 先将 t 的信息放⼊ 2 号哈希表中；
b. 初始化⼀些变量：左右指针： left = 0，right = 0 ；⽬标⼦串的⻓度： len = 
INT_MAX ；⽬标⼦串的起始位置： retleft ；（通过⽬标⼦串的起始位置和⻓度，我们就
能找到结果）
c. 当 right ⼩于字符串 s 的⻓度时，⼀直下列循环：
i. 将当前遍历到的元素扔进 1 号哈希表中；
ii. 检测当前窗⼝是否满⾜条件：
• 如果满⾜条件：
◦ 判断当前窗⼝是否变⼩。如果变⼩：更新⻓度 len ，以及字符串的起始位置
retleft ；
◦ 判断完毕后，将左侧元素滑出窗⼝，顺便更新 1 号哈希表；

◦ 重复上⾯两个过程，直到窗⼝不满⾜条件；
iii. right++ ，遍历下⼀个元素；
d. 判断 len 的⻓度是否等于 INT_MAX ：
i. 如果相等，说明没有匹配，返回空串；
ii. 如果不相等，说明匹配， 返回 s 中从 retleft 位置往后 len ⻓度的字符串。

代码实现：

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0}; // 统计字符串 t 中每⼀个字符的频次int kinds = 0;        // 统计有效字符有多少种for (auto ch : t)if (hash1[ch]++ == 0)kinds++;int hash2[128] = {0}; // 统计窗⼝内每个字符的频次int minlen = INT_MAX, begin = -1;for (int left = 0, right = 0, count = 0; right < s.size(); right++) {char in = s[right];if (++hash2[in] == hash1[in])count++;           // 进窗⼝ + 维护 countwhile (count == kinds) // 判断条件{if (right - left + 1 < minlen) // 更新结果{minlen = right - left + 1;begin = left;}char out = s[left++];if (hash2[out]-- == hash1[out])count--; // 出窗⼝ + 维护 count}}if (begin == -1)return "";elsereturn s.substr(begin, minlen);}
};

小结：本文介绍了滑动窗口的进阶用法，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！