不定长滑动窗口---初阶篇

目录

引言

求最长/最大

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

3090. 每个字符最多出现两次的最长子字符串

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

1208. 尽可能使字符串相等

904. 水果成篮

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

2958. 最多 K 个重复元素的最长子数组

2024. 考试的最大困扰度

1004. 最大连续1的个数 III

1658. 将 x 减到 0 的最小操作数

求最短/最小

209. 长度最小的子数组

2904. 最短且字典序最小的美丽子字符串

求子数组个数

越长越合法型

1358. 包含所有三种字符的子字符串数目

2962. 统计最大元素出现至少 K 次的子数组

3325. 字符至少出现 K 次的子字符串 I

2799. 统计完全子数组的数目

越短越合法型

713. 乘积小于 K 的子数组

3258. 统计满足 K 约束的子字符串数量 I

2302. 统计得分小于 K 的子数组数目

LCP 68. 美观的花束

恰好型滑动窗口

930. 和相同的二元子数组

1248. 统计「优美子数组」

3306. 元音辅音字符串计数 II

992. K 个不同整数的子数组

加餐

1438. 绝对差不超过限制的最长连续子数组

2401. 最长优雅子数组

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

总结

---

引言

继上一篇关于《定长滑动窗口》的分析，本文将会重点分析不定长滑动窗口这一算法，不定长滑动窗口毫无疑问其窗口的大小是不确定的，其他就与定长滑动窗口一样了，解题思想还是：入窗口---更新答案---出窗口。依旧结合灵神分享的算法题单对每个题目进行解析。ps:本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。

定长滑动窗口---初阶篇-CSDN博客文章浏览阅读758次，点赞37次，收藏25次。滑动窗口基于暴力解法的优化，将时间复杂度降到线性，解题时的关键是定义好循环不变量。掌握好滑动窗口，可以进一步提升你的算法能力和解题效率。本文将帮助读者正确的使用滑动窗口，理解其应用场景。https://blog.csdn.net/2401_87944878/article/details/147719085

求最长/最大

不定长滑动窗口第一类题型：求最大值/求最长范围。本类题型解法：通过维护一段区间，控制题干的临界范围来找到最大值或最大范围，下面将根据具体题目进行分析。

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

题解：使用滑动窗口，在没有重复字符时持续入，当有重复字符时就出窗口。

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> ss; //存储已经存在的字符int left=0,n=s.size();int ret=0;for(int right=0;right<n;right++){while(ss.count(s[right]))   //如果当前字符已经存在，需要出窗口{ss.erase(s[left++]);}ss.insert(s[right]);  //进窗口ret=max(ret,right-left+1);   //更新答案}return ret;}
};

3090. 每个字符最多出现两次的最长子字符串

题解：与上一题一样，还是采用滑动窗口的方式进行解决。

class Solution {
public:int maximumLengthSubstring(string s) {unordered_map<char,int> m;int n=s.size(); int left=0,ret=0;for(int right=0;right<n;right++){m[s[right]]++;while(m[s[right]]==3)  //当该字符已经出现过2次时，进行出窗口{m[s[left++]]--;}ret=max(ret,right-left+1);}return ret;}
};

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

题解：控制一个区间，保证这个区间内最多存在一个0，返回这个区间中1的个数。通过滑动窗口来控制这一段区间，当0的个数大于1时进行出窗口，否则入窗口。

class Solution {
public:int longestSubarray(vector<int>& nums) {//控制一个区间，保证这个区间内最多存在一个0，返回这个区间中1的个数//还是使用滑动窗口进行解决，当0的个数超过1的时候出窗口，否则入窗口int left=0,zero=0;  //用zero记录0的个数int ret=0,n=nums.size();for(int right=0;right<n;right++){if(nums[right]==0) zero++;while(zero==2)if(nums[left++]==0) zero--;//更新答案ret=max(ret,right-left); //注意：此处1的个数是right-left，因为是闭区间所以总个数+1,//但是区间中有一个是0}return ret;}
};

1208. 尽可能使字符串相等

题解：维护一段区间保证这一区间内开销始终小于maxCost，当开销大于max的时候进行出窗口，否则继续入窗口。

class Solution {
public:int equalSubstring(string s, string t, int maxCost) {//控制一个区间，当该区间内的开销大于最大开销的时候进行出窗口，否则入窗口int left=0,n=min(s.size(),t.size());int ret=0,tmp=0;for(int right=0;right<n;right++){   tmp+=abs(s[right]-t[right]);while(tmp>maxCost){tmp-=abs(s[left]-t[left]);left++;}//更新答案ret=max(ret,right-left+1);}return ret;}
};

904. 水果成篮

题解：维护一段区间，保证这段区间种水果种类最多有2种，返回这段区间长度最大值。

class Solution {
public:int totalFruit(vector<int>& fruits) {//还是控制一段区间，保证这一区间内水果种类小于等于2即可，返回最长区间unordered_map<int ,int> m;  //存储水果数种类及个数int n=fruits.size(),left=0;int ret=0;for(int right=0;right<n;right++){m[fruits[right]]++;while(m.size()==3)   //此时说过种类有3种{m[fruits[left]]--;if(m[fruits[left]]==0) m.erase(fruits[left]);left++;}ret=max(ret,right-left+1);}return ret;}
};

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

题解：维护一段区间，保证区间内每个元素只出现过一次。返回这段区间内元素之和的最大值。

class Solution {
public:int maximumUniqueSubarray(vector<int>& nums) {//维护一段区间，保证区间内每个元素仅出现一次，返回区间元素最大总和unordered_set<int> ss;int left=0,n=nums.size();int ret=0,tmp=0;for(int right=0;right<n;right++){while(ss.count(nums[right]))  //进行出窗口{tmp-=nums[left];ss.erase(nums[left++]);}ss.insert(nums[right]);  //入窗口tmp+=nums[right];ret=max(ret,tmp);   //调整答案}return ret;}
};

2958. 最多 K 个重复元素的最长子数组

题解：维护一段区间，保证这段区间内相同元素个数不超过k个，返回区间最长长度。

class Solution {
public:int maxSubarrayLength(vector<int>& nums, int k) {//控制一段区间，使得该区间内元素出现频率小于等于k//返回最长区间长度int left=0,n=nums.size();unordered_map<int ,int> mm;int ret=0;for(int right=0;right<n;right++){mm[nums[right]]++;//入窗口while(mm[nums[right]]>k)   //相同元素超过k个，出窗口mm[nums[left++]]--;ret=max(ret,right-left+1);}return ret;}
};

2024. 考试的最大困扰度

题解：K决定了我们可以改变的字符个数，维护一段区间，当这段区间的T或者F的个数有一个是小于K的就能够实现让区间内字符相同。当T和F的个数都大于K的时候就需要出窗口。

class Solution {
public:int maxConsecutiveAnswers(string answerKey, int k) {//维护一段区间，保证区间内T和F的个数至少有一个小于k即可int left=0,n=answerKey.size();int ret=0,Tnum=0,Fnum=0;  //分别记录T和F的个数for(int right=0;right<n;right++){if(answerKey[right]=='T') Tnum++;else Fnum++;while(Tnum>k&&Fnum>k)  //当该段区间内T和F的个数都大于K的时候就需要进行出窗口{if(answerKey[left++]=='T') Tnum--;else Fnum--;}ret=max(ret,right-left+1);}return ret;}
};

1004. 最大连续1的个数 III

题解：本题与上面的《删除一个元素以后全是1的最长子字符串》类似，不同的是此时可以通过将0修改为1来找最长子串。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {//本题与上面的删除一个元素以后全是1的最长子字符串类似//本题是将K个0变成1int left=0,n=nums.size();int ret=0,zero=0;for(int right=0;right<n;right++){//入窗口if(nums[right]==0) zero++;  while(zero>k)if(nums[left++]==0) zero--;  //出窗口//更新答案ret=max(ret,right-left+1);}return ret;}
};

1658. 将 x 减到 0 的最小操作数

题解：左右两边元素之和是x----->中间部分元素之和是sum-x即可。通过将维护左右两边区间转化为维护中间部分来让滑动窗口的使用根方便自然。

class Solution {
public:int minOperations(vector<int>& nums, int x) {//需要移除左右两边的元素---->移除中间部分的元素//将题型转化为移除中间部分的元素，方便滑动窗口的使用//左右两边元素之和是x，则中间元素之和是sum-x，找到中间最长区间//计算中间部分需要的和int sum=0,n=nums.size();for(auto e:nums) sum+=e;  int mid=sum-x;if(mid<0) return -1;  //当mid小于都等于0的时候是没有区间满足条件的需要特殊处理if(mid==0) return n;//使用滑动窗口int left=0,num=0,tmp=0;for(int right=0;right<n;right++){tmp+=nums[right];while(tmp>mid)tmp-=nums[left++];if(tmp==mid) num=max(num,right-left+1);}return num==0?-1:n-num;}
};

求最短/最小

求最短长度/求最小值与最大值类型相同，仅仅是将取最大值修改为取最小值。只不过需要注意更新答案的位置应该在哪。

209. 长度最小的子数组

题解：经典的滑动窗口问题，此题需要注意的是更新答案的位置与上面的有所区别。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {//经典的滑动窗口问题int n=nums.size();int left=0;int ret=INT_MAX,tmp=0;  //for(int right=0;right<n;right++){tmp+=nums[right];while(tmp>=target){ret=min(ret,right-left+1);tmp-=nums[left++];}  }return ret==INT_MAX?0:ret;}
};

2904. 最短且字典序最小的美丽子字符串

题解：通过滑动窗口遍历字符串，当区间中1的个数是k个就对结果进行更新并且进行出窗口操作。

class Solution {
public:string shortestBeautifulSubstring(string s, int k) {//通过滑动窗口遍历字符串，找到最小的长度且最小字典序int n=s.size();int left=0;int one=0;string ret;for(int right=0;right<n;right++){if(s[right]=='1') one++;   //入窗口while(one==k){string tmp=s.substr(left,right-left+1);  int a=ret.size(),b=tmp.size();if(a==0||a>b||(a==b&&ret>tmp)) ret=tmp;      //更新窗口if(s[left++]=='1') one--;   //出窗口}}return ret;}
};

求子数组个数

越长越合法型

滑动窗口有两层循环，当内循环结束以后恰好不满足条件，但是[left-1,right]是恰好满足的，如果将数组进一步向左边延申其都是满足的，所以可以将ret+=left；当right走到下一个位置之后如果left到right区间内还是不满足，则right可以作为右边界，此时[left，right]依旧是恰好满足的；当right走到下一个位置之后如果left到right区间是满足的，此时就可以对left进行更新了，让left更靠前，使得right向后的时候能够更早的与left形成恰好满足的情况。

1358. 包含所有三种字符的子字符串数目

题解：通过滑动窗口找到恰好满足条件的位置，将ret+=left即可，可以结合上面图解分析。

class Solution {
public:int numberOfSubstrings(string s) {//此题在找到恰好满足条件的数组后，对该数组进行拓展即可，越长越合法//采用滑动窗口进行实现int n=s.size(),left=0,ret=0;unordered_map<char ,int > count;  //存储各个字符出现的次数for(int right=0;right<n;right++){count[s[right]]++;while(count.size()==3){//此时的子字符串满足条件//开始找恰好满足条件的之子字符串if(--count[s[left]]==0) count.erase(s[left]);left++;}//此时已经不满足条件了，但是left的上一次还是满足的//所以[left-1,right]区间内是恰好满足的字符串，将left-1向左拓展依旧是满足的//所以可以将ans+=left  ret+=left;               }return ret;}
};

2962. 统计最大元素出现至少 K 次的子数组

题解：与上一题相同，还是找恰好满足的情况。

class Solution {
public:long long countSubarrays(vector<int>& nums, int k) {//先找到最大元素，再进行滑动窗口找恰好满足的位置int themax=INT_MIN;for(auto e:nums)if(e>themax) themax=e;int count=0; //统计最大元素的个数int n=nums.size(),left=0;long long ret=0;for(int right=0;right<n;right++){if(nums[right]==themax) count++;  while(count==k)if(nums[left++]==themax) count--;  //出窗口ret+=left;  //更新答案}return ret;}
};

3325. 字符至少出现 K 次的子字符串 I

题解：使用map对每个字符进行统计，还是找恰好满足的情况。

class Solution {
public:int numberOfSubstrings(string s, int k) {//有一个字符至少出现K次，还是找恰好满足的情况unordered_map<char ,int > mm; //统计各个字符出现的次数int ret=0;int n=s.size(),left=0;for(int right=0;right<n;right++){mm[s[right]]++;  //进窗口while(mm[s[right]]==k)mm[s[left++]]--;  //出窗口ret+=left;  //更新答案}return ret;}
};

2799. 统计完全子数组的数目

题解：子数组中不同元素的数目等于整个数组不同元素的数目----->子数组中至少包含nums中不同元素中的一个。所以此处就转化为了"越长越合法型"，向前找都是合法的。

class Solution {
public:int countCompleteSubarrays(vector<int>& nums) {//题目要求子数组中不同元素的数目等于数组中不同元素的数目//这就意味着子数组中包含nums所有种类的数字至少一个//还是找恰好满足条件的情况//向统计nums中存在多少个不同的元素unordered_map<int,int> count;for(auto e:nums) count[e]++;int differ=count.size();//进行滑动窗口unordered_map<int,int> mm;int n=nums.size();int ret=0,left=0;for(int right=0;right<n;right++){mm[nums[right]]++;   //入窗口while(mm.size()==differ){if(--mm[nums[left]]==0) mm.erase(nums[left]);  //出窗口left++;         }ret+=left;  //更新答案}return ret;}
};

越短越合法型

与越长越合法型恰好相反，此题是越短越合法。滑动窗口的内存循环用于解决不满足条件的区间，在外层循环中直接对答案进行更新，在外层循环中[left,right]是满足条件的，那以right为终点，[left+1,right]，[left+2,right]，[left+2,right].......[right-1,right]，[right,right]都是满足条件的，所以直接将ret+=right-left+1即可。因为righ是一直在向后面走的，所以不会出现重复的区间。

713. 乘积小于 K 的子数组

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {//越短越合法if(k<=1) return 0;int left=0,n=nums.size();int ret=0;long long tmp=1;for(int right=0;right<n;right++){tmp*=nums[right];   //入窗口while(tmp>=k)//不满足条件      tmp/=nums[left++];  //出窗口ret+=right-left+1; //更新答案}return ret;}
};

3258. 统计满足 K 约束的子字符串数量 I

题解：依旧是越短越合法型，通过内循环解决不满足条件的情况，在对ret进行更新即可。

class Solution {
public:int countKConstraintSubstrings(string s, int k) {//越短越符合条件int zero=0,one=0;int ret=0,left=0,n=s.size();for(int right=0;right<n;right++){if(s[right]=='1') one++;  //入窗口else zero++;while(zero>k&&one>k){if(s[left]=='1') one--;  //出窗口else zero--;left++;}ret+=right-left+1;  //更新答案}return ret;}
};

2302. 统计得分小于 K 的子数组数目

题解：区间越小越满足条件，符合越短越合法模型。

class Solution {
public:long long countSubarrays(vector<int>& nums, long long k) {//子数组的长度越小越满足条件int n=nums.size();int left=0;long long tmp=0,ret=0;for(int right=0;right<n;right++){tmp+=nums[right];  //入窗口while(tmp*(right-left+1)>=k){tmp-=nums[left++];  //进行出窗口}ret+=right-left+1;   //更新答案}return ret;}
};

LCP 68. 美观的花束

题解：先找到一个满足条件的区间，对该区间进行缩小所得到的子区间依旧是满足条件的。

class Solution {#define MOD 1000000007
public:int beautifulBouquet(vector<int>& flowers, int cnt) {//找到一个满足的区间，将该区间进行缩小得到的所有子区间也是同样满足条件的int n=flowers.size();int left=0,ret=0;unordered_map<int ,int> mm;for(int right=0;right<n;right++){mm[flowers[right]]++;  //入窗口while(mm[flowers[right]]>cnt)   mm[flowers[left++]]--; ///出窗口ret=(ret+right-left+1)%MOD;  //更新答案}return ret;}
};

恰好型滑动窗口

与前两个不同的是此时是恰好满足，比如要求找一个子数组的长度恰好等于K的数组个数，可以转化长度长度>=K的数组个数减去长度>=K+1的数组个数，或者是转化为长度<=K的数组个数减去长度<=K+1的数组个数来实现。关于恰好型滑动窗口的关键在于将其转化为越短越合法型或越长越合法型。

930. 和相同的二元子数组

题解：对题意进行转化，将等于goal的条件转化为大于等于goal的个数减去大于等于goal-1的个数即可，或者转化为小于等于goal的个数减去大于等于goal的个数即可。下面题解采用第二种进行代码实现。

class Solution {
public://找小于等于k的数组个数int numMore(vector<int> nums,int k){int n=nums.size();int left=0,tmp=0;int ret=0;for(int right=0;right<n;right++){tmp+=nums[right];   //进窗口while(left<=right&&tmp>k) tmp-=nums[left++];  //出窗口ret+=right-left+1;  //更新答案}return ret;}int numSubarraysWithSum(vector<int>& nums, int goal) {return numMore(nums,goal)-numMore(nums,goal-1);}
};

1248. 统计「优美子数组」

题解：将恰好转化为至少或者是至多来间接解决。

class Solution {
public://恰好有K个奇数的子数组个数=大于等于K个奇数的子数组个数-大于等于K+1个奇数的子数组个数int numMore(vector<int>& nums,int pos){int n=nums.size(),left=0;int ret=0,odd=0;for(int right=0;right<n;right++){if(nums[right]%2==1) odd++;  //进窗口while(left<=right&&odd>=pos) if(nums[left++]%2==1) odd--;   //出窗口ret+=left;  //更新答案}return ret;}int numberOfSubarrays(vector<int>& nums, int k) {return numMore(nums,k)-numMore(nums,k+1);}
};

3306. 元音辅音字符串计数 II

题解：恰好有k个辅音字母的个数==大于等于k个辅音字母的个数-大于等于k+1个辅音字母的个数。通过哈希表来记录区间中元音字符的种类和个数，再使用一个变量来统计区间内辅音字符的个数即可。

class Solution {unordered_set<char> vowel;  //记录元音
public://恰好包含K个辅音==至少包含K个辅音-至少包含K+1个辅音long long numMore(string str,int pos){unordered_map<char ,int> num;  //记录区间中元音的类型及个数int n=str.size(),left=0;int conson=0;  //记录辅音的个数long long ret=0;for(int right=0;right<n;right++){if(vowel.count(str[right])) num[str[right]]++;  //进窗口else conson++;while(left<=right&&num.size()==5&&conson>=pos){if(vowel.count(str[left]))    //出窗口{if(--num[str[left]]==0) num.erase(str[left]);}else conson--;left++;}ret+=left;  //更新答案}return ret;}long long countOfSubstrings(string word, int k) {vowel={'a','e','i','o','u'};return numMore(word,k)-numMore(word,k+1);}
};

992. K 个不同整数的子数组

题解：恰好有k个整数不同的个数==有大于等于k个不同整数的个数-有大于等于k+1个不同整数的个数。

class Solution {
public://不同整数的个数恰好为K=不同整数的个数大于等于K-不同整数的个数大于等于K+1int numMore(vector<int>& nums,int pos){unordered_map<int ,int> mm;int left=0;int n=nums.size(),ret=0;for(int right=0;right<n;right++){mm[nums[right]]++;     //进窗口while(mm.size()>=pos){if(--mm[nums[left]]==0) mm.erase(nums[left]);   //出窗口left++;  }ret+=left;   //更新答案}return ret;}int subarraysWithKDistinct(vector<int>& nums, int k) {return numMore(nums,k)-numMore(nums,k+1);}
};

加餐

1438. 绝对差不超过限制的最长连续子数组

题解：通过map对nums中最大值和最小值的记录来判断是不是合理区间。

class Solution {
public:int longestSubarray(vector<int>& nums, int limit) {//使用滑动窗口来控制区间[left,right]map<int,int> mm;int n=nums.size(),left=0;int ret=0;for(int right=0;right<n;right++){mm[nums[right]]++;  //进窗口while(mm.rbegin()->first-mm.begin()->first>limit){if(--mm[nums[left]]==0) mm.erase(nums[left]);  //出窗口left++;}ret=max(ret,right-left+1);  //更新答案}return ret;}
};

2401. 最长优雅子数组

题解：使用滑动窗口来记录一个区间中二进制的总和(通过|来确定)，再进行按位与&判断是否为0；此题的关键在于二进制的增加和删除。通过|将二进制位进行整合，通过^将不符合要求的二进制进行删除。

class Solution {
public://将每一个数字的每一个二进制位记录下来，当一个二进制位已经存在时就说明不满足条件int longestNiceSubarray(vector<int>& nums) {int n=nums.size(),ret=0;int left=0,tmp=0;for(int right=0;right<n;right++){while(tmp&nums[right]) tmp^=nums[left++];   //出窗口，通过^实现将前面数字的二进制移除tmp|=nums[right];      //入窗口，通过|将当前数字的二进位加入ret=max(right-left+1,ret);//更新答案}return ret;}
};

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

题解：通过控制一段长度与p长度相等的区间来判断区间是否满足题意即可。

class Solution {
public:vector<int> findAnagrams(string s, string p) {//使用滑动窗口，判断当前区间中的字符个数是否与目标字符串个数相同char tar[128]={0};  //存储p中字符的种类及个数int num=0;  //存储p中不同字符的个数for(auto e:p) if(tar[e]++==0) num++;vector<int> ret;int n=s.size(),left=0,same=0;char ch[128]={0};   //存储区间中字符的种类及个数for(int right=0;right<n;right++){if(++ch[s[right]]==tar[s[right]]) same++;if(right-left+1==p.size())  //当区间长度与p的长度相等时进行判断{if(same==num) ret.push_back(left);if(ch[s[left]]==tar[s[left]]) same--; ch[s[left++]]--;}}return ret;}
};

总结

不定长滑动窗口就是根据题目确定条件来对窗口进行控制，还是采用：进窗口---更新答案---出窗口的三个步骤。

文章题目内容很长，感谢阅读。