目录

什么是滑动窗口：

一、长度最小的子数组：

二、无重复字符的最长子串：

三、找到字符串中所有的异位词

四、串联所有单词的子串：

---

什么是滑动窗口：

滑动窗口是双指针的一种升级版：

当使用双指针算法的时候，发现左右两个指针可以不回退，这个时候就可以升级成滑动窗口算法了。

滑动窗口整体思路：

1、通过left = 0，right = 0来确定窗口。

2、接着依次进窗口，判断，出窗口。

3、就提论题，在合适的位置更新结果。

通过上述思路发现滑动窗口的整体代码是差不多的，虽然看着有两个循环所以看着时间复杂度是o(N^2)级别的，但是实际上每次只移动了一步，所以是o(N)级别的。

一、长度最小的子数组：

题目出处：

209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/description/题目说明：

示例说明：

如上所示：

在题目所给示例中，可以看到最短的数组可以是一个，也可能不存在，这里要注意，如果不存在的话，这个时候right肯定就越界了，此时就不能够进行访问了。

解题思路：

首先需要left和right作为滑动窗口的边界，定义sum作为和target比较，len来作为长度返回值

定义完变量后，进行进窗口的操作（其实就是将right指针向右移动一位，这样的话left和right之间的值就会增加）

接着判断，如果此时sum<target,那么就还需要值来使sum变大。就继续进行进窗口的操作

但是如果此时sum>=target，那么就需要重置len，将len重置为原来len和此时窗口中数据的个数中小的那一个。此时sum>=target并且len也找到此时left为左边界中最小的了如果继续进窗口就没意义了，所以就进行出窗口的操作（就是将left++，在left++之前将sum减去++之前的left所在的值），然后继续判断，sum和target之间的大小关系。回到了上述黄色的接着判断。

最后，可能如上述例三中，那样的话记得判断一下，因为像例三那样的len是肯定大于了这个数组的长度，不存在出窗口，这个时候就可以判断和数组大小的关系，也可以用三目运算符进行判断

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0;int sum = 0, len = INT_MAX;while (right < nums.size()){//首先进窗口sum += nums[right];while(sum >= target)//判断{len = min(len,right-left+1);sum -= nums[left];left++;}right++;}if (len > nums.size()) len = 0;return len;}
};

二、无重复字符的最长子串：

题目出处：

3. 无重复字符的最长子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/题目说明：

示例说明：

如图所示每当从right多加上一个字符（进窗口）的时候，进行判断，如果加的字符串有重复的就删除left所处的字符串（出窗口）

如上图所示，最长的子串就是a上述画红线的，均为3，所以最长子串就是3。

同理，在示例2中只有一个字符，所以就是1。

在示例3中，wke作为最长字符串就是3。

解题思路：

总体来说就是4个步骤：进窗口，判断，出窗口，更新结果。

在本题中：

1、unordered_multiset容器来判断是否出窗口，left和right来维护窗口，ret作为返回结果

2、对于本题：

首先将right处的字符insert到容器st中进行记录，接着判断这个right处的字符是不是重复的

如果是就将left处的字符容器st中删除，并将left++，直到容器st里面没有重复字符，

然后再更新结果，从ret和right-left+1中取大的作为结果。

最后++right

上述作为循环直到right>n。

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_multiset<char> st;int left = 0, right = 0, n = s.size();int ret = 0;while (right < n){//进窗口st.insert(s[right]);//判断while (st.count(s[right]) > 1){//出窗口st.erase(st.find(s[left]));left++;}//更新结果ret = max(ret, right - left + 1);right++;}return ret;}
};

三、找到字符串中所有的异位词

题目出处：

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/题目说明：

示例说明：

如上所示：

子串的异位词在我看来就是一个和子串长度相等的字符串，其中，在子串出现的字母在异位词中也出现相同的次数。

解题思路：

1、首先要解决：如何判断两个字符串是异位词

我们可以使用两个哈希表，题目示例所示，将一个字符串中的字符搞到哈希表1里面，然后将另一个字符串中的字符搞到哈希表2里面，比较的时候判断哈希表里面的值是否相等。

在此题，我们可以使用一个数组来代替哈希表（毕竟知道这些字符串就在a~z之间），然后在判断的时候就可以直接判断某个位置的数字大小是否相等即可，如果每个位置的大小都相等就是异位词，否则就不是异位词

2、滑动窗口+哈希表：

既然是滑动窗口的题目就依然是进窗口，判断，出窗口，更新结果：

在使用滑动窗口之前要将p字符串里面的字符都放到一个哈希表（数组）hash1中。

维护s字符串用left和right，进窗口就是进right位置的字符，出窗口就是出left位置的字符

进窗口：对于本题就是将s字符串中的字符进入一个到哈希表（数组）中，也就是hash2[in]++,in提前在s中取此次进窗口的字符。

判断：每当right和left之间的长度比p字符串的长度大的时候，就需要出窗口了，

出窗口：将s字符串中的left位置字符从哈希表（数组）中删除，也就是hash2[out]--,out提前定义在s中的left位置的字符。

更新结果：在出窗口后，就可以根据两个数组是否相等的结果来更新结果。

3、优化：

上述的方法写一个函数来进行判断两个数组是否相等是可行的，并且在oj题中也不会超时，但是还有一种更好的方法，使用变量count来统计窗口中的有效字符的个数：

有效字符：当进窗口之后，如果此时进窗口的那个字符in在hash2的位置小于等于hash1的位置，那么就证明这个字符进来后是有效的，也就是这个字符在p中能够被找到并且此时不大于p中这个字符的出现次数，在判断后就需要将count++。

在出窗口之前，如果此时出窗口的那个字符out在hash2的位置小于等于hash1的位置，那么就证明这个字符是有效字符出去的，也就是这个字符在p中能够被找到并且此时不大于p中这个字符的出现次数，在这个字符出去后就要将count--。

最后在更新结果的时候：如果count == p的大小的话就证明此时left的位置 往后的 p的长度 的字符串就是p的异位词，定义一个vector尾插进去，最后返回这个vector即可。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26] = {0};int hash2[26] = {0};for(auto e : p) hash1[e - 'a']++;int left = 0,right = 0,count = 0;while(right < s.size()){char in = s[right];//进窗口hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a']) count++;if(right-left+1 > p.size()){//出窗口char out = s[left];if(hash2[out-'a'] <= hash1[out-'a']) count--;hash2[out - 'a']--;left++;}right++;if(count == p.size()) ret.push_back(left);}return ret;}
};

四、串联所有单词的子串：

题目出处：

30. 串联所有单词的子串 - 力扣（LeetCode）https://leetcode.cn/problems/substring-with-concatenation-of-all-words/题目说明：

示例说明：

解题思路：

本题和第三题基本是差不多的，第三题是哈希表中的是字符，第四题是哈希表中给字符串

以上面示例一为例子：

首先，和第三题差不多，用一个哈希表hash1来存储words的信息，用另一个哈希表hash2来存储字符串中的在窗口中的子字符串，最后比较二者即可，但是这题不能够用数组代替，因为这里的哈希表是<string,int>的哈希表。

然后搞出滑动窗口的四步：

进窗口：对于本题就是将s字符串中的子字符串进入一个到哈希表中，也就是hash2[in]++,in提前在s中取此次进窗口的子字符（用substr函数）

判断：每当right和left之间的长度比words中的各个字符串的长度乘以字符串的个数，大的时候，就需要出窗口了，

出窗口：将s字符串中的left位置和往后len个字符从哈希表中删除（len就是每个子字符串的个数）也就是hash2[out]--

更新结果：在出窗口后，就可以根据两个数组是否相等的结果或者像第三题那样的count的结构是否相等来判断更新结果。

示例代码：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;for(auto& e : words) hash1[e]++;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]++;//维护countif(hash2[in] <= hash1[in]) count++;if(right - left + 1 > m*len){//出窗口：string out = s.substr(left,len);if(hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}if(count == m) ret.push_back(left);}}return ret;}
};