刷题交流｜滑动窗口总结

list

1876. 长度为三且各字符不同的子字符串

窗口的状态是什么？

字符种类

怎么表示该状态？

map 存字符次数，cnt 存种类个数

什么时候滑动？

固定大小，直接滑

class Solution {

public:

int countGoodSubstrings(string s) {

int l=0;

int r=0;

int res=0;

int cnt=3;

map m;

for (r=0;r<3;r++){

if (m[s[r]]==0){

cnt--;

}

m[s[r]]++;

}

if (cnt==0){

res++;

}

while(r < s.size()) {

if (m[s[l]]==1){

cnt++;

}

m[s[l]]--;

if (m[s[r]]==0){

cnt--;

}

m[s[r]]++;

l++;

r++;

if (cnt==0){

res++;

}

}

return res;

}

};

3. 无重复字符的最长子串

求子串，典型的滑动窗口题型。

任意给定一个窗口，问

窗口中的状态是什么？怎么得到可行解？

是否有重复元素

具体怎么表示该状态？

对于是否有重复元素，很自然的想法自然是用个 map 来存取。

什么是否扩展窗口？怎么寻找可行解？

当下一个字符没有出现时，即没有在 map 中记录时，就向右移动，新窗口就是一个可行解

什么时候收缩窗口？怎么优化可行解？

当下一个字符出现过时，说明当前窗口左边界需要移动了，需要移动到和新字符相同字符处。然后又固定左边界，向右寻找可行解，实际上这一步不应该叫优化可行解，只是转换另一个可行解的范围而已。要得到最右解，还得每次判断长度。

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int l = 0;

int r = 0;

map c;

int length =0;

while(r < s.size()) {

if (length < (r-l)) {

length = r-l;

}

while (c[s[r]] && l < r) {

c.erase(s[l]);

l++;

}

c[s[r]] = true;

r++;

}

if (length < (r-l)) {

length = r-l;

}

return length;

}

};

1695. 删除子数组的最大得分

窗口中的状态是什么？

每个元素都独一无二,求和

怎么刻画该状态？

用哈希表

什么时候扩展？

当下一个元素不存在时

什么时候收缩？

当下一个元素存在时，且收缩到下一个元素相同元素处

class Solution {

public:

int maximumUniqueSubarray(vector& nums) {

int l=0;

int r= 0;

int sum=0;

int max=0;

unordered_map m;

while(r

sum+=nums[r];

m[nums[r]]=true;

r++;

max=max>sum?max:sum;

while (l < r && r

sum-=nums[l];

m[nums[l]]=false;

l++;

}

}

return max;

}

};

187. 重复的 DNA 序列

第一步是读题，认识到题的本质。这题的本质就是：求重复的子串，长度为 10

窗口中的状态是什么？

出现次数

怎么刻画该状态？

哈希表

什么时候移动？

直接移

class Solution {

public:

vector findRepeatedDnaSequences(string s) {

int l=0;

int r=9;

unordered_map m;

vector res;

string t;

while(r

t=s.substr(l,10);

m[t]++;

if (m[t]==2) {

res.push_back(t);

}

l++;

r++;

}

return res;

}

};

219. 存在重复元素 II

这题并不难，难点在于识别它可以使用滑动窗口来做。这种题若能认清它的本质，就很简单了。

nums [i] = nums [j] 即表明有重复元素，而i 和 j 的差的 绝对值 至多为 k的意思，即表示窗口最大为 k。

那么，我们就可以识别这个题的本质了：就是窗口固定为 k，并且判断窗口中是否有重复元素。

窗口的状态是什么？

重复元素

怎么刻画该状态？

用个哈希表记录下即可

由于是固定窗口大小，所以不存在什么时候收缩问题，直接判断，然后整体移动即可。

class Solution {

public:

bool containsNearbyDuplicate(vector& nums, int k) {

int l = 0;

int r = 0;

unordered_map m;

while(r

if (r

if (m[nums[r]]) {

return true;

}

m[nums[r]]=true;

r++;

} else {

if (m[nums[r]]) {

return true;

}

m[nums[r]]=true;

m[nums[l]]=false;

r++;

l++;

}

}

return false;

}

};

220. 存在重复元素 III

这题和 219 很像，重点都是要认清题的本质

条件 abs(i - j) <= k 和上一题一样，都是指窗口最大为 k+1，自然移动时直接固定窗口为 k+1 即可。**

而另一个条件 abs(nums[i] - nums[j]) <= t 则是指窗口中，最接近的两个数之间的距离，要小于 t。换句话说，就是要找到最接近的两个数。

窗口的状态是什么？

最接近的两个数

怎么表达该状态？

这个题要比以前常见的滑动窗口要复杂一些，一般滑动窗口表达状态都是 O(1) 的，而这题显然 O(1) 做不到。比较自然的想法有先排序再遍历，以及遍历的基础上二分，时间复杂度都是 O(klogk).

固定窗口自然也不用考虑什么伸缩，直接移动即可。

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {

if (nums.empty()) {

return false;

}

long mm;

int l = 0;

int r=k+1;

vector tm =nums;

// 整个数组就是一个窗口时

if ((k+1) >= nums.size()) {

sort(nums.begin(),nums.end());

for (int i = 0;i < nums.size()-1;i++) {

mm = abs((long)nums[i]-(long)nums[i+1]);

if (mm<=t) {

return true;

}

}

return false;

}

// 窗口较小，移动

while(r<=nums.size()) {

nums=tm;

cout << endl;

sort(nums.begin()+l,nums.begin()+r);

for (int i = l;i < r-1;i++) {

mm= abs((long)nums[i]-(long)nums[i+1]);

cout << mm << endl;

if (mm<=t) {

return true;

}

}

l++;

r++;

}

return false;

}

};

窗口移动 O(n),排序 O(klogk)，总的时间复杂度为 O(nk∗logk).

不出以外，最后超时了。

我们来思考一下，为什么排序会超时。

我们求的是什么？固定窗口内，求似乎存在两个数相距小于 k，而我们排序的目的是为了找出所有相邻数的距离，但是目的却是只要一个就满足了，那么自然会超时了，因为做了很多多余的工作。

那么我们可不可以求窗口里最接近的两个数呢？这个算法可以在 O(n) 内解决，似乎比排序要快了许多。答案是不可以，因为最接近的两个数实际上是距离最小的一个，但是我们实际上只要找到满足某个范围的就可以了。因此还是比较麻烦。

回想一下，滑动窗口优化的原理是什么：下一个窗口的解利用上一个窗口的结果，比如数组的和，积，字符频率等等，都是这样做的。

但是实际上还有一种跟自然的想法，那就是用个数据结构来组织这些元素，那么窗口滑动时只要增删一个元素就行了，自然满足利用上一个窗口的结果了，比如滑动窗口最大值，就是用单调队列来做的。而这个题我们也需要这么做，在寻找合适数据结构之前，先让我们再来分析一下题目。

我们的目的是找到 abs(nums[i] - nums[j]) <= t 满足，换句话说，对于 num[i]，如果我们能够在窗口里找到 [num[j]-t,num[j]+t] 的元素，那么就满足了。

那我们可以简化题目了，假设固定了个窗口，我们只对于左端点那个点，去余下窗口元素去寻找是否在这个范围里的值，如果不存在，那么窗口就往后移动一个点，这样起始点就只右移了一次。一直这样右移，那么对于所有的点，都能进行一次查找对应范围里的数（刚开始需要初始化窗口，最后窗口也在缩小，只有中间是固定大小的）。

那么，问题就转换为，怎么用一个数据结构组织一些数，然后能够迅速的找到某个范围里的元素了。

或者我们再简化一下，右移范围是固定的，我们可以转换为，寻找比下界大的第一个数，是否在上界范围里。也就是说，看窗口里的数比 num[j]-t 大的元素，是不是小于 num[j]+t，如果在的话，那么就满足了。而很巧，要查找比某数大的数，自然数据要有序才行，而有序的数据结构，要么二叉树，要么数组链表什么。

但是我们的窗口还需要增删元素，所以增删的时间复杂度不能太高，数据又要有序，并且能找到第一个比某个数大的数，这么一组合，自然答案就是红黑树了。

窗口里的状态是什么？

比左端点 -t 大的第一个数的值

怎么表示该状态？

用红黑树组织窗口里的元素

什么时候窗口扩展？

初始化 k+1 窗口大小，之后直接平移

什么时候窗口收缩？

当右窗口达到端点后，窗口就需要慢慢收缩了。

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {

int l =0;

int r=0;

set s;

if (k>=nums.size()) {

k=nums.size()-1;

}

for (r=0;r<=k;r++){

s.insert(nums[r]);

}

if (s.size()!=(k+1)){

return true;

}

while(l

cout << endl;

s.erase(nums[l]);

auto m = s.lower_bound((long)nums[l]-t);

if ((m !=s.end()) && (long)(*m) <= ((long)nums[l]+t)) {

return true;

}

if (r

int mm=s.size();

s.insert(nums[r]);

if (mm==s.size()) {

return true;

}

r++;

}

l++;

}

return false;

}

};

1493. 删掉一个元素以后全为 1 的最长子数组

窗口的状态是什么？

窗口中只含一个 0

怎么刻画该状态？

用个变量即可

什么时候扩展？

直接扩展

什么时候收缩？

如果有两个 0 就收缩

class Solution {

public:

int longestSubarray(vector& nums) {

int cnt=0;

int l = 0;

int r= 0;

int length=0;

vector t(2);

while(r

t[nums[r]]++;

if (t[0]==2) {

length=length>(r-l-1)?length:(r-l-1);

}

r++;

while(l

t[nums[l]]--;

l++;

}

}

if (t[0]==0) {

length=nums.size()-1;

} else if (t[0]==1) {

length=length>(r-l-1)?length:(r-l-1);

}

return length;

}

};

76. 最小覆盖子串

求子串，典型的滑动窗口题型

窗口中的状态是什么？可行解是什么？

含有 t 字符串中的所有字符，并且出现次数也相同。

怎么表示该状态？

用一个 hash 来存，存什么？存目标字符串 t 中的所有字符

什么时候窗口扩展？怎么寻找可行解？

一直右移，直到窗口内不包含可行解。

什么时候窗口收缩？怎么优化可行解？

把左边那些多余的字符全部去掉，包括不存在的字符和多余的字符。

class Solution {

public:

string minWindow(string s, string t) {

map m;

int l = 0;

int r = 0;

int cnt = 0;

int length = 0;

int begin = 0;

int end = 0;

for (int i = 0;i < t.size();i++) {

m[t[i]]++;

cnt++;

}

while (r < s.size()) {

if (m.count(s[r]) != 0) {

if (m[s[r]] > 0) {

cnt--;

}

m[s[r]]--;

}

r++;

while(cnt == 0 && l < r) {

if (m.count(s[l]) == 0) {

l++;

} else if (m[s[l]] < 0) {

m[s[l]]++;

l++;

} else {

if (length == 0 || (length > (r-l))) {

length = r-l;

begin = l;

end = r;

}

m[s[l]]++;

l++;

cnt++;

}

}

}

return s.substr(begin,end-begin);

}

};

手搓了一遍后，发现了很多细节，技巧等东西，但是总的来说，这题的原理并不复杂，就是一个简单的滑动窗口，每次扩展窗口找到所有的元素，然后收缩多余的元素，如果左边界的字符必须满足，说明这时窗口不能再收缩了，就更新下长度坐标什么的。然后右移元素，这时窗口又不满足了，所以又扩展。

具体的细节和技巧有两个：1. 怎么表示字符是否满足。2. 怎么判断窗口中的元素是否满足。

第一个的问题我用的一个 map，value 就是这个字符还需要的个数。而判断窗口是否满足，理论上来说需要遍历 map 看是否所有 value 都 ≤ 0，这里就用了个小技巧，就是每次收缩和扩展时维护一个 cnt，这个 cnt 表示一个还需要满足的字符数。然后通过判断这个数就知道窗口中的元素是否满足。

632. 最小区间

我们先来分析题目：

定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。这句话的意思是说，区间长度越小，或者长度相等，但是在数轴前方，则说区间更小。

找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。这句话很容易理解了，就是找个区间让每个组包含至少一个数。这个和我们以前做的字符频率题目有点像，需要满足字符的出现频率。

我们先假设只有两个区间，要找目的区间的话，显然要分两区间是否相交，

若相交，如 [1,3] [2,4]，要找到相交的区间 [2,3] 即可。

若不相交，如 [1,2], [3,4] 则显然要找中间的那个区间 [2,3]

无效的图片地址

由于原数组给定是点而不是连续的值，所以结果也应该是点的集合。相交应该是 {2}，不相交应该是 {2,3}.

看出什么了吗？要找区间都有的数，显然要看它们之间重合的关系，而且画图非常的清晰，那么我们就来把所有的区间都画在一个数轴上。

对于 [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] 这个区间集合 （其实不应该叫区间，毕竟并不是连续的，容易误解人）。

画出来应该是这样的：

无效的图片地址

而我们要找的是一个区间，这个区间满足一个性质：

至少每个区间都有一个数

区间长度足够小

区间长度相等时，数轴前面的更小

比如

无效的图片地址

包含 {0,4,5} 三个数的区间就满足这个性质，那么结果就是 [0,5]，区间长度为 5.

是不是觉得很眼熟？如果数变成字符，所有数组成一个字符串，区间种类组成另一个字符串，那么不就是要寻找一个子串，使得子串包含所有目标字符串出现的字符吗？并且长度还要最小。是的，这个题目就是 76 最小覆盖子串问题。

那么这个题就很简单了，先把区间全部合并成一个数组，数组的元素是一个 struct，包含数字和属于的区间种类，数组按数字排序。然后滑动窗口使窗口包含所有区间种类，并且长度最小。

窗口的状态是什么？

区间的种类

怎么表示该状态？

用个 hash 表表示具体种类的出现次数，然后用个 cnt 计算出现的种类个数

什么时候窗口扩张？

种类不满足时

什么时候窗口收缩？

种类满足后，收缩到刚好减少一个种类的时候，再寻找新的解

struct item {

int val;

int index;

};

bool cmd(item i1,item i2) {

return i1.val

}

class Solution {

public:

vector smallestRange(vector>& nums) {

vector arr;

int l=0;

int r=0;

int length=9999999;

int tmpR=0;

int tmpL=0;

int cnt=nums.size();

vector res;

vector m(nums.size());

// 预处理数组

for (int i=0;i

for (int j=0;j

item it;

it.val=nums[i][j];

it.index=i;

arr.push_back(it);

}

}

sort(arr.begin(),arr.end(),cmd);

// 下面和最小覆盖子串差不多

while(r

// cout << "arr[l].val:" << arr[l].val << " arr[l].index:" << arr[l].index << " arr[r].val:" << arr[r].val << " arr[r].index:" << arr[r].index << " m[arr[r].index]: " << m[arr[r].index] << " cnt:"<

if (m[arr[r].index]==0){

cnt--;

}

// cout << cnt << endl;

m[arr[r].index]++;

while((l1)){

// cout<<"##"<

m[arr[l].index]--;

l++;

}

if (cnt==0){

// cout<< arr[l].val << " " << arr[r].val <

if (length>(arr[r].val-arr[l].val)){

length=arr[r].val-arr[l].val;

tmpL=arr[l].val;

tmpR=arr[r].val;

// cout << tmpR << " " << tmpL<

}

m[arr[l].index]--;

l++;

cnt++;

}

r++;

}

res.push_back(tmpL);

res.push_back(tmpR);

return res;

}

};

面试题 17.18. 最短超串

跟 76. 最小覆盖子串 基本一样

窗口中的状态是什么？

字符的频率

怎么刻画该频率？

用哈希表来记录每一个字符的频率，用一个 maxCnt 记录还需要满足的字符数

为了判断新字符是否满足，故哈希表的初始值存储匹配字符串中的字符，初始值就表示还需要满足的字符数。而每次满足一个，值则减一。

什么时候窗口扩展？

当字符不是要求字符时，扩展

当有字符不满足时，扩展，也就是直到窗口中满足条件为止

什么时候窗口收缩？

当左边界的字符不是要求字符，或者该字符是要求字符，但是出现次数超出要了需求次数，收缩。

class Solution {

public:

vector shortestSeq(vector& big, vector& small) {

int l=0;

int r= 0;

vector res;

int maxCnt=small.size();

int min=0;

int begin=0;

int end=0;

bool has=false;

unordered_map m;

// 预处理 small 数组

for (int i =0;i < small.size();i++) {

m[small[i]]++;

}

while(r < big.size()) {

// 不是要求字符，则直接跳过

if (m.count(big[r])==0) {

r++;

continue;

}

if (m[big[r]]>0){

maxCnt--;

}

m[big[r]]--;

// 当左边界不是要求字符时直接收缩

// 或者，当窗口符合，并且左边界的字符不只一个时，收缩

while ((l < r) && ( (m.count(big[l])==0)||(m[big[l]]<0) )) {

if (m.count(big[l])==0) {

l++;

continue;

}

m[big[l]]++;

l++;

}

// 符合要求后，直接更新

if (maxCnt==0 && (min > (r-l) || min == 0)) {

has=true;

min=(r-l);

begin=l;

end=r;

}

r++;

}

if (has) {

res.push_back(begin);

res.push_back(end);

}

return res;

}

};

这里有一个小优化的点，即收缩时，如果左边界的字符是需求字符，那么先不收缩，先直到窗口扩展到所有字符都条件之后再收缩。

这时窗口中已经满足了条件，因此窗口收缩是为了寻找下一个可行解。根据最小变化法，上一个可行解进行最小的变化然后生成新的可行解。上一个可行解假设已经含有了 k 个字符，只需减少一个字符，即含有 k-1 个字符，然后再寻找新字符进行生成即可。

故当窗口满足条件后，窗口开始收缩，并且收缩到只包含 k-1 个字符，并且下一个字符是必须字符。也就是说，再收缩一次就只含 k-2 个字符了。

class Solution {

public:

vector shortestSeq(vector& big, vector& small) {

int l=0;

int r= 0;

vector res;

int maxCnt=small.size();

int min=0;

int begin=0;

int end=0;

bool has=false;

unordered_map m;

// 预处理 small 数组

for (int i =0;i < small.size();i++) {

m[small[i]]++;

}

while(r < big.size()) {

// 不是要求字符，则直接跳过

if (m.count(big[r])==0) {

r++;

continue;

}

if (m[big[r]]>0){

maxCnt--;

}

m[big[r]]--;

// 当左边界不是要求字符时直接收缩

// 或者，当窗口符合，并且左边界的字符不只一个时，收缩

// 此处优化了下

while ((l < r) && ( (m.count(big[l])==0)||( (maxCnt==0)&&(m[big[l]]<0) ) )) {

if (m.count(big[l])==0) {

l++;

continue;

}

m[big[l]]++;

l++;

}

// 符合要求后，直接更新

if (maxCnt==0 && (min > (r-l) || min == 0)) {

has=true;

min=(r-l);

begin=l;

end=r;

}

r++;

}

if (has) {

res.push_back(begin);

res.push_back(end);

}

return res;

}

};

细节有点多，不过还算中等，和 76，567 等题一样要求字符频率满足。简单来说，这题的难点也像普通的变长窗口一样，即什么窗口伸缩。

扩展：当字符不是要求字符，或者是要求字符，但是出现频率不满足时

收缩：当字符不是要求字符，或者是要求字符，但是出现频率高于需求时 。

567. 字符串的排列

和 76 题差不多，都是判断字符的频率，76 要求出具体的子串，这题只判断是否存在即可。并且这题子串长度也固定了，窗口大小也固定了。

任意给定一个不满足的窗口（满足就返回了），这时什么时候扩展？什么时候收缩？

窗口中的状态是什么？可行解是什么？

字符串的排列，换句话说，字符频率相同

怎么表示该状态？

用 hash 来存频率，用一个 cnt 来计算还需要满足的字符个数。

什么时候扩展窗口？怎么寻找可行解？

当下一个元素不存在时，整个窗口都可以跳过这个元素，因为是连续的。

而当下一个元素存在时，并且已经满足时，就要窗口收缩到该元素满足的左边界。

当下一个元素存在且不满足时，则移动

什么时候收缩窗口？怎么优化可行解？

而当下一个元素存在时，并且已经满足时，就要窗口收缩到该元素满足的左边界。

如果当固定窗口来做的话，确定一个窗口就遍历 map 判断，那样就退化成 O(n2) 了，和暴力没区别。故这题要当非固定窗口。只是扩展的时候，条件复杂一点。扩展和收缩的时候要维护 cnt。

class Solution {

public:

bool checkInclusion(string s1, string s2) {

if (s1.size() > s2.size()) {

return false;

}

int cnt = s1.size();

int cntTmp = cnt;

int l=0;

int r= 0;

map m;

map tmp;

for (int i = 0;i

m[s1[i]]++;

tmp[s1[i]]++;

}

while(r<=s2.size()){

// cout << l << " " << r << " " << cnt<< " " << s2[r]<

// for (auto i = m.begin();i!=m.end();i++){

// cout << i->first << " " << i->second << endl;

// }

if (cnt==0) {

return true;

}

if (m.count(s2[r]) == 0) { // 下一个元素不存在

// cout << "case 1" << endl;

l = r+1; // 跳过

r=l;

m=tmp;

cnt=cntTmp;

} else if (m[s2[r]] > 0){ // 下一个元素不满足

// cout << "case 2" << endl;

m[s2[r]]--;

cnt--;

r++;

} else { // 下一个元素满足或过于满足

// cout << "case 3" << endl;

// cout << "##: " << l << " " << r << " " << s2[l] <<" " << s2[r] << endl;

while(true) {

if (s2[l]==s2[r]) {

l++;

r++;

break;

} else {

m[s2[l]]++;

cnt++;

l++;

}

}

}

}

return false;

}

};

这题其实要说复杂也不复杂，就是 map 记录频率，cnt 用来记录还有多少个字符没满足，滑动的时候，根据下一个元素究竟满足与否，需不需要等，然后判断窗口的收缩。不过这题我还是 debug 了很久。

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

这个题和 567 题差不多，都是求字符的频率。不过 567 只用满足一次，而这个题则是需要找出所有满足的字符串。之前 567 题思路是使用不定的窗口，然后根据当前窗口的长度，下一个字符是否存在，下一个字符是否满足，出的字符与入的字符是否相等等几个要点来确定窗口的伸缩策略。这样写了一会，感觉过于复杂。故放弃。状态图如下

无效的图片地址

看了下题解，发现使用固定窗口的方法更加便捷。

用数组代替 map，用比较数组代替比较 map 或 cnt，怎么说呢，比较技巧性，不过也很巧妙。暴力的思路基本差不多，不过就是每次固定移动一个窗口后，这个窗口对于的数组都需要重新生成一遍，而滑动窗口则在上一次的基础上改动。

class Solution {

public:

vector findAnagrams(string s, string p) {

vector res;

if(s.size()

return res;

}

vector s_m(26);

vector p_m(26);

int l=0;

int r=p.size()-1;

for (int i=0;i

p_m[p[i]-'a']++;

s_m[s[i]-'a']++;

}

if (p_m==s_m){

res.push_back(0);

}

while(r< (s.size()-1)){

s_m[s[l]-'a']--;

l++;

r++;

s_m[s[r]-'a']++;

if(p_m==s_m){

res.push_back(l);

}

}

return res;

}

};

比较容易理解：

使用两个长度为 26 的数组记录字符串中字符的频率

窗口固定

每次移动一个元素，然后入一个元素，出一个元素

每次比较两频率数组

移动窗口的复杂度是 O(n)，每次比较数组虽然次数看着较多，不过由于和问题规模无关，并且是固定的比较小，故仍然视为 O(1)，整体来看时间复杂度还是 O(1)。这个思路相对于暴力改进的地方在于：每次确定窗口都要重新计算频率数组，计算的过程是 O(n)，但是滑动窗口则与上一次的数组相关，降为了 O(1).

这种方法还是比较暴力的，根据上面我们第一种思路，如果当前窗口满足了，下一个入的字符和出的字符又相等的话，那么可以直接得出结果，而不是判断数组。故优化如下：

class Solution {

public:

vector findAnagrams(string s, string p) {

vector res;

if(s.size()

return res;

}

vector s_m(26);

vector p_m(26);

int l=0;

int r=p.size()-1;

bool f=false;;

for (int i=0;i

p_m[p[i]-'a']++;

s_m[s[i]-'a']++;

}

if (p_m==s_m){

res.push_back(0);

f=true;

}

while(r< (s.size()-1)){

if (f){

if (s[l]==s[r+1]){

l++;

r++;

res.push_back(l);

} else {

f=false;

s_m[s[l]-'a']--;

l++;

r++;

s_m[s[r]-'a']++;

}

} else {

s_m[s[l]-'a']--;

l++;

r++;

s_m[s[r]-'a']++;

if(p_m==s_m){

res.push_back(l);

f=true;

}

}

}

return res;

}

};

思路很简单，两个点，上一个窗口是否满足，以及移出的字符和移入的字符是否相等，分为四种情况。

904. 水果成篮

这题的最难点在于读懂题目。。

简单来说，就是窗口中最多有 2 种不同的数

窗口中的状态是什么？

窗口种数的种类最多 2 个

怎么刻画该状态？

用一个 cnt 记录种类个数，用一个 map 记录具体每个种类的个数

什么时候窗口扩展？

直接扩展

什么时候窗口收缩？

当种类 == 3 的时候收缩，并且收缩到有一个出现次数为 0，即种类为 2 时结束。

class Solution {

public:

int totalFruit(vector& fruits) {

int l=0;

int r=0;

int cnt=0;

unordered_map m;

int length=0;

while(r

if (m[fruits[r]]==0){

cnt++;

}

m[fruits[r]]++;

r++;

if (cnt==3) {

length=length>(r-l-1)?length:(r-l-1);

}

while(l

if (m[fruits[l]]==1) {

cnt--;

}

m[fruits[l]]--;

l++;

}

}

length=length>(r-l)?length:(r-l);

return length;

}

};

1456. 定长子串中元音的最大数目

窗口中的状态是什么？

元音字母的个数

怎么刻画该状态？

用个变量

什么时候伸缩？

固定窗口大小，直接移动即可

class Solution {

public:

int maxVowels(string s, int k) {

int length=0;

int l=0;

int r=0;

int cnt=0;

int max=0;

while(r

max=max>cnt?max:cnt;

if (r

if (s[r]=='a' || s[r]=='e' || s[r]=='i'||s[r]=='o'||s[r]=='u') {

cnt++;

}

r++;

continue;

}

if (s[r]=='a' || s[r]=='e' || s[r]=='i'||s[r]=='o'||s[r]=='u') {

cnt++;

}

if (s[l]=='a' || s[l]=='e' || s[l]=='i'||s[l]=='o'||s[l]=='u') {

cnt--;

}

l++;

r++;

if (cnt==k) {

return k;

}

}

max=max>cnt?max:cnt;

return max;

}

};

485. 最大连续 1 的个数

窗口中的状态是什么？

1 的个数

如何表示该状态？

一个 cnt 变量

什么时候扩展？

当下一个元素是 1 时

什么时候收缩？

当下一个元素是 0 时

class Solution {

public:

int findMaxConsecutiveOnes(vector& nums) {

int r=0;

int cnt=0;

int max=0;

while(r

if (nums[r]==0) {

if (max < cnt) {

max=cnt;

}

cnt=0;

r++;

} else {

cnt++;

r++;

}

}

if (max < cnt) {

max=cnt;

}

return max;

}

};

emmm，最近再刷滑动窗口，顺手按滑动窗口来做的，遇 0 收缩遇 1 伸展，不过写着写着发现每次收缩都是清空了窗口，说明遍历后的数字一点用都没用，直接把 l 的操作去掉了。。。就变成了遍历一遍。。感觉这题说明了一些滑动窗口的应用场景。简单来说，如果窗口伸展之后的新窗口，和旧窗口的元素重合的话，那么旧可以用滑动窗口来生成新窗口，而这题则没有重合，所以滑动窗口并无法优化。

1004. 最大连续 1 的个数 III

这题和 485 类似，不过 1 之间可以有 k 个 0.换句话说，窗口中可以有 k 个零，这样新旧窗口就会重合了，可以用滑动窗口来做。

窗口中的状态是什么？

很多个 1 ，最多 k 个 0

怎么表示该状态？

需要记录一下 0 的个数

什么时候窗口扩张？

当窗口中 0 的个数小于 k 时，或者窗口中元素等于 0，但下一个元素为 1

什么时候窗口收缩？

当窗口中的个数等于 0 时，并且，下一个元素也为 0

class Solution {

public:

int longestOnes(vector& nums, int k) {

int l = 0;

int r = 0;

int cnt = 0;

int max= 0;

while(r

if (cnt == k && nums[r] == 0) {

if (max < (r-l)) {

max=r-l;

}

while(nums[l]==1) {

l++;

}

l++;

cnt--;

} else {

if (nums[r]==0){

cnt++;

}

r++;

}

}

if (max < (r-l)) {

max=r-l;

}

return max;

}

};

424. 替换后的最长重复字符

这题和 1004 有点像，都是替换然后求重复的最长长度，不过这题数组中元素的种类变多了，上一题只有两种状态。

窗口中的状态是什么？

很多个 x 字符，最多 k 个其它字符。

怎么刻画该状态？

需要记录其它字符的个数

什么时候窗口伸展？

其它字符的个数小于 k 或其它字符的个数等于 k 且下一个字符不是其它字符

什么时候窗口收缩？

其它字符的个数等于 k 且下一个字符也是其它字符

上面的分析与 1004 基本一样，问题就在于，其它字符是什么？或者说，怎么知道重复的字符，这个字符是什么？这样才好确定其它字符。

假定给定了一个窗口，怎么确定重复的字符是哪个？

很显然，要使得最后重复的字符个数最多，自然应该选择当前状态下，重复次数最多的那个字符。现在问题就转换为，我怎么知道这个出现频率最多的字符是哪个呢？或者说，是否需要自己维持字符的出现频率呢？或者只维持最大值？

简单看了一下一些题解的思路，发现基本思路就是自己维护一个当前窗口字符的频率。

class Solution {

public:

int characterReplacement(string s, int k) {

int l = 0;

int r = 0;

int cnt=k;

int max=0;

vector m(26);

int index=0;

char c=s[0];

char tmp;

int all;

while(r

if (s[r]==c) {

m[s[r]-'A']++;

r++;

} else {

if (cnt > 0) {

m[s[r]-'A']++;

r++;

cnt--;

} else {

if (s[l]!=c && cnt < k) {

cnt++;

}

max=max>(r-l)?max:(r-l);

m[s[l]-'A']--;

l++;

}

}

tmp=c;

all=0;

for (auto i =0;i < 26;i++) {

all+=m[i];

if (m[tmp-'A'] < m[i]) {

tmp=i+'A';

}

}

if (c!=tmp) {

c = tmp;

cnt=k-(all-m[tmp-'A']);

} else if (l==r) {

c=s[l];

cnt=k;

}

}

max=max>(r-l)?max:(r-l);

return max;

}

};

窗口的收缩，需要根据下一个字符以及当前窗口中字符的频率。

当下一个字符等于重复字符时，扩展

当下一个字符不等时，且可替换字符大于 0 时，扩展

当下一个字符不等时，且可替换字符小于等于 0 时，收缩

每次窗口变化后，都要根据字符频率来判断是否要更新重复字符。如果更新了，那么可替换字符也要随之变化。

上面就是这样实现的，但是效率较低。观察发现，每次判断是否更新时，都是通过遍历 map 来判断的。我们可以通过维护一个当前最大频率的次数来优化。

class Solution {

public:

int characterReplacement(string s, int k) {

int l = 0;

int r = 0;

int cnt=k;

int max=0;

vector m(26);

char c=s[0];

int all;

while(r

cout << endl;

// cout << l << s[l] << endl;

if (s[r]==c) {

cout << "case1" << endl;

m[s[r]-'A']++;

r++;

} else {

if (cnt > 0) {

cout << "case2" << endl;

m[s[r]-'A']++;

r++;

cnt--;

cout << l << " " << c<<" "<< s[r] <<" "<

if (r < s.size() && (m[s[r]-'A'] == m[c-'A']) && (cnt==0) && (s[r]!=c)) {

cout << "###" << endl;

all=0;

for (auto i =0;i < 26;i++) {

all+=m[i];

}

// cout << s[r] << endl;

c=s[r];

cnt=k-(all-m[s[r]-'A']);

r++;

cout << c << " " << cnt << endl;

}

} else {

cout << "case3" << endl;

max=max>(r-l)?max:(r-l);

cout << s[l] << " " << c << endl;

if (s[l]!=c && cnt < k) {

cnt++;

}

m[s[l]-'A']--;

l++;

cout << l << " " << c<<" "<< s[r] <<" "<

if (r < s.size() && (m[s[r]-'A'] == m[c-'A']) && (cnt==0) && (s[r]!=c)) {

cout << "###" << endl;

all=0;

for (auto i =0;i < 26;i++) {

all+=m[i];

}

c=s[r];

cnt=k-(all-m[s[r]-'A']);

r++;

}

}

}

if (l==r) {

c=s[l];

cnt=k;

}

}

max=max>(r-l)?max:(r-l);

return max;

}

};

优化了之后，发现代码过于复杂，猜测思路出现了问题。查看题解，发现有更简单的伸缩方式。上面我们的思路是：根据下一个字符与重复字符是否相等，以及可替换的次数等分情况伸缩的。因此还需要维护一个重复字符，这种方式过于复杂。

更简单的思路如下：不考虑什么是否扩展，每次直接扩展一格。扩展之后，直接记录长度，重复字符等数，只记录当前状态，不考虑以前的状态和下一个状态。

扩展后，先找出最大频率的出现次数，然后看其它出现的次数和是否大于可替换次数，如果大于，则收缩，否则扩展。这样就把状态之间的解耦了，不用分析具体的字符是什么。

class Solution {

public:

int characterReplacement(string s, int k) {

vector m(26);

int l = 0;

int r = 0;

int all;

int max;

int length=0;

while(r

length=length>(r-l)?length:(r-l);

m[s[r]-'A']++;

r++;

max=0;

all=0;

for (int i = 0;i < 26;i++) {

all+=m[i];

if (max < m[i]) {

max = m[i];

}

}

while ((all-max) > k) {

m[s[l]-'A']--;

l++;

all--;

}

}

length=length>(r-l)?length:(r-l);

return length;

}

};

上面就是直接先扩展，然后再对窗口内的元素进行判断，扩展没有理由。但是上面还是有一个拖慢效率的点，那就是每次计算窗口内最大值时，需要遍历 map，但是实际上真的需要遍历 map 吗？实际上每次窗口增加一次后，只有一个字符的频率变了，我们只需要用这个频率和上一次的最大次数比较就行了，那样就从 O（n）降到了 O（1），如下

class Solution {

public:

int characterReplacement(string s, int k) {

vector m(26);

int l = 0;

int r = 0;

int all=0;

int max=0;

int length=0;

while(r < s.size()) {

m[s[r]-'A']++;

max=max>(m[s[r]-'A'])?max:(m[s[r]-'A']);

r++;

all++;

for (int i=all-max;i > k;i--) {

m[s[l]-'A']--;

l++;

all--;

}

length=length>(r-l)?length:(r-l);

}

return length;

}

};

最后击败 95%，差不多优化到了极限。

这道题经过多次优化和分析，最后才 ac 得不错，我们来分析下这题的要点。

这题重复元素有多个，不像 1004 只有两个，故需要计算字符频率

计算字符频率可以用哈希表，不过这题字符特殊，都是大写字符，所以可以用数组简化

扩展窗口时，可以根据字符状态，重复字符等当前窗口的状态来决定，也可以直接扩展后再更新窗口，而否则更简单

计算最大频率字符时，可以只比较上一个最大值和当前更新的字符来简化遍历 map

674. 最长连续递增序列

这题不是滑动窗口，收缩的时候直接把窗口缩没了，不过有些题和它类似，故作为前提做一下

class Solution {

public:

int findLengthOfLCIS(vector& nums) {

int l=0;

int r=1;

int length=1;

while(r

if (nums[r] > nums[r-1]) {

r++;

continue;

}

length=length>(r-l)?length:(r-l);

// 和一般滑动窗口的区别就在这，这题直接缩没了。

l=r;

r++;

}

length=length>(r-l)?length:(r-l);

return length;

}

};

1839. 所有元音按顺序排布的最长子字符串

这题和 674 类似，都是求窗口中元素满足大小关系的子串。不过这题可以相等，并且增加了出现频率的限制，因此这题收缩时就有条件了，换句话说，可以用滑动窗口来做了。

这题要求元音都出现比较好做，就是一个字符频率，和常见的频率题一样，用哈希表和种类变量即可。问题是元音的排序，如果按照字符匹配的思想，即判断字符是什么，再去判断是否收缩非常麻烦。故利用计算机中字符的存储特性，元音的 ASCII 码是单调递增的，故直接比较数字大小即可。

窗口中的状态是什么？

元音都要出现，且递增

怎么表示该状态？

hash 表和 cnt 变量管理频率,由于共 5 个元素，故用数组代替 hash 表。

什么时候窗口扩展？

下一个元素大于等于当前元素时，并且若第一个字符不是 a，那么直接跳过。

什么时候窗口收缩？

下一个元素小于当前元素就收缩，问题是收缩到什么时候。

假设 112342，当遇到 42 时要开始收缩了，由于完整的结果一定是从 1 开始，故收缩其实是直接跳过窗口。（？）

窗口扩展完后就要判断是否满足了条件，然后更新结果。

class Solution {

public:

int longestBeautifulSubstring(string word) {

int l=0;

int r=1;

int maxCnt=4;

int length=0;

while(r

// 当所有元素都满足时

if (maxCnt==0) {

length=length>(r-l)?length:(r-l);

}

// 当第一个元素不是 a 时

if (maxCnt==4 && word[r-1]!='a'){

l=r;

r++;

if (length>(word.size()-l)){

return length;

}

continue;

}

// 当后一个元素等于当前元素时跳过

if (word[r-1] == word[r]) {

r++;

continue;

}

// 当后一个元素相邻大于该元素时

if (valid(maxCnt,word[r-1],word[r])) {

maxCnt--;

} else { // 后一个元素小于或大于不只一个

l=r;

maxCnt=4;

}

r++;

}

if (maxCnt==0) {

length=length>(r-l)?length:(r-l);

}

return length;

}

bool valid(int cnt,char a,char b) {

if (cnt == 4 && a=='a' && b == 'e') {

return true;

}

if (cnt == 3 && a=='e' && b == 'i') {

return true;

}

if (cnt == 2 && a=='i' && b=='o') {

return true;

}

if (cnt == 1 && a=='o' && b=='u') {

return true;

}

return false;

}

};

好吧，这题和 674 一样，其实是个前后指针的题，根本不是滑动窗口。

395. 至少有 K 个重复字符的最长子串

我认为这题可以很好的加深我们对滑动窗口的理解，究竟什么时候能够使用滑动窗口。滑动窗口的单调性是什么。

有人说是左端点固定，最优解的右端点单调不减，我试了这题，应该是满足的，那么就应该能用滑动窗口才对。

但是，如果按一般的滑动窗口思维来看，右端点右移是寻找解，左端点收缩是优化可行解，但是这题显然不一样，因为这题右端点移动时，反而是寻找解和可行解一起做。而左端点右移只是换下一个解而已。

如果按这个思维来做，那么右端点右移时什么时候才知道是最优解呢？不可能提前知道的，只能移动到末尾，那么下一次左端点右移时，就必然设计右端点回溯问题，这样显然不再是滑动窗口了。

我看了题解，通过限制了窗口里的字母种类，这样在窗口扩展时，就有一个什么时候停止的限制。但是我没有理解，单调性究竟是什么单调？为什么单调就能解了？

1234. 替换子串得到平衡字符串

类似一些应用题，这个题的难点也在于读懂题目，并且转换为熟悉的模型。

这个题要使所有字符出现次数都为 n/4，而 n 是给定的，换句话说，字符的初始出现频率我们是知道的，并且最后要转换成的频率我们也是知道的。

然后题目要我们寻找到一个子串，子串是连续的，先不管要求是什么，寻找子串问题我们就可以想到滑动窗口了。

我们来看子串需要满足的条件：子串中的任何一个元素，都替换成另一个字母，然后使得频率符合要求。既然是需要替换成另一个字母，那么被替换的字母肯定减少了，新的字母频率又增加了。

换句话说，子串应该是由频率比目标频率 n/4 高的字母组成的，而又要求子串长度最短，那么自然的，就应该是要使得子串包含所有这些高频率字母了。

既然使得找高频率的字母，那么自然的，就要先把这些字母求出来了，令人高兴的是，这些可以直接求出来。

窗口的状态是什么？

包含高频率字母

怎么表示该状态？

用个 cnt 既然还需要满足的个数，用个哈希表判断是否是高频率字母

什么时候窗口扩展？

当高频率字母没有包含完时

什么时候窗口收缩？

高频率包含完后，如果左边界不是高频率字母，收缩优化解。然后再收缩一次出一个高频率解，再扩展寻找解。

class Solution {

public:

int balancedString(string s) {

int l=0;

int r=0;

int cnt=0;

int length=999999;

int m=s.size()/4;

vector t(26);

// 求初始频率

for (int i=0;i

t[s[i]-'A']++;

}

// 计算高频率字母，并且值为出现次数

for (int i =0;i<26;i++) {

if (t[i] > m) {

cnt += (t[i]-m);

t[i]-=m;

} else {

t[i]=-999;

}

}

if (cnt==0){

return 0;

}

while(r

if (t[s[r]-'A'] > 0){// 右端点是待入高频率字母

cnt--;

t[s[r]-'A']--;

} else if (t[s[r]-'A']!=-999) {// 是已经满足了的高频率字母

t[s[r]-'A']--;

}

// 当左端点是非高频字母，或多出的高频字母，收缩，即优化解

while(l < r && cnt == 0 && (t[s[l]-'A'] != 0)){

if (t[s[l]-'A']!=-999){

t[s[l]-'A']++;

}

l++;

}

// 求长度，并左端点右移一个，即出一个高频字母

if (cnt==0){

length=length<(r-l+1)?length:(r-l+1);

cnt++;

t[s[l]-'A']++;

l++;

}

r++;

}

return length;

}

};

30. 串联所有单词的子串