目录
3298. 统计重新排列后包含另一个字符串的子字符串数目 II
本篇博客是继上一篇的续写，上一篇博客【入门算法】不定长滑动窗口：从动态调整到精准匹配以灵活特性实现高效破题-CSDN博客介绍了不定长滑动窗口的使用场景及方法，以及一些常见的面试题型，本篇博客将对不定长滑动窗口题型进行进一步深入，本章的题目有难度需要有一定的不滑动窗口思想。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
求最长/最大
2730. 找到最长的半重复子字符串
题解：使用滑动窗口，控制窗口内相邻字符相等的数量最多是1个。
class Solution {
public:
int longestSemiRepetitiveSubstring(string s) {
//通过滑动窗口来实现
int n=s.size();
int left=0,count=0; //count记录窗口中相邻字符相等的个数
int ret=1;
for(int right=1;right<n;right++)
{
if(s[right-1]==s[right]) count++; //相邻字符相等
while(count>1) //出窗口
{
if(s[left]==s[left+1]) count--;
left++;
}
ret=max(ret,right-left+1); //更新答案
}
return ret;
}
};2779. 数组的最大美丽值
题解：先对数组进行排序，再使用滑动窗口；通过滑动窗口控制左右两端之差不超过2*k即可。
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
//先对数组进行排序
//再通过滑动窗口来找最大美丽值
int n=nums.size();
sort(nums.begin(),nums.end());
int left=0,ret=0;
for(int right=0;right<n;right++)
{
while(nums[left]+k<nums[right]-k) left++; //此时窗口的最大值和最小值相差太大，进行出窗口
ret=max(ret,right-left+1); //更新答案
}
return ret;
}
};1838. 最高频元素的频数
题解：排序+滑动窗口；先对数组进行排序，方便使用最小的k得到最多的频数。使用滑动窗口控制区间中需要递增的中次数不超过k。
class Solution {
public:
int maxFrequency(vector<int>& nums, int t) {
//先对数组进行排序
int n=nums.size();
sort(nums.begin(),nums.end());
int left=0,ret=1;
long long k=t;
for(int right=1;right<n;right++)
{
//如果当前位置与上一个元素位置不相同，需要将前面所有元素进行递增
if(nums[right]>nums[right-1]) k-=((long long)right-left)*((long long )nums[right]-nums[right-1]);
while(k<0) //当递增的次数大于k，要进行出窗口
{
if(nums[left]<nums[right]) k+=nums[right]-nums[left];
left++;
}
ret=max(ret,right-left+1); //更新答案
}
return ret;
}
};2516. 每种字符至少取 K 个
class Solution {
public:
int takeCharacters(string s, int k) {
int ch[3]={0};
for(auto e:s) ch[e-'a']++; //统计字符串中各个字符的总个数
for(int i=0;i<3;i++)
{
ch[i]-=k; //计算删去左右两边后中间区间各个字符最多出现的个数
if(ch[i]<0) return -1;
}
int n=s.size();
int left=0,ret=0;
for(int right=0;right<n;right++)
{
ch[s[right]-'a']--; //入窗口
while(ch[0]<0||ch[1]<0||ch[2]<0) //当中间区间字符出现的次数大于可以出现的次数进行出窗口
{
ch[s[left]-'a']++; //出窗口
left++;
}
ret=max(ret,right-left+1); //更新答案
}
return n-ret;
}
};2831. 找出最长等值子数组
题解： 滑动窗口；以滑动窗口的最左侧作为窗口中相同的值，控制窗口内不同值的个数少于k即可。
class Solution {
public:
int longestEqualSubarray(vector<int>& nums, int k) {
int n = nums.size();
unordered_map<int, int> count;
count[nums[0]]++;
int right=1,ret=0;
for(int left=0;left<n;left++)
{
//right-left表示窗口长度,count[nums[left]]表示窗口类相同值个数
while (right < n && k >= right - left - count[nums[left]]) //保持窗口内不同个数小于k
{
count[nums[right]]++; //进行入窗口
right++;
}
ret = max(ret, count[nums[left]]); //更新答案
count[nums[left]]--; //出窗口
}
return ret;
}
};求最短/最小
求最短长度/求最小值与最大值类型相同，仅仅是将取最大值修改为取最小值。只不过需要注意更新答案的位置应该在哪。
1234. 替换子串得到平衡字符串
题解：找一个子字符串，对子字符串中字符进行替换实现平衡字符串，找到最短子字符串即可。题目中将这一字符串称为待替换子串，应该如何找最短待替换字串？？？待替换字串以外的所有种类字符的个数都满足小于等于平均值。正难则反，通过关注待替换子串以外的每种字符的个数来确定其是否满足要求即可。
class Solution {
public:
int balancedString(string s) {
//题目希望找到一个字符串，该字符串经过替换之后能够让字符串s称为平衡字符串、
//若待替换子串意外存在出现此处大于m的就不能实现替换
unordered_map<char ,int> mm;
for(auto e:s) mm[e]++;
int n=s.size(),aver=n/4;
if(mm['Q']<=aver&&mm['W']<=aver&&mm['E']<=aver&&mm['R']<=aver) return 0;
//进行滑动窗口
int left=0,ret=INT_MAX;
for(int right=0;right<n;right++)
{
mm[s[right]]--; //入窗口
while(mm['Q']<=aver&&mm['W']<=aver&&mm['E']<=aver&&mm['R']<=aver)
{
ret=min(ret,right-left+1); //更新答案
mm[s[left++]]++; //出窗口
}
}
return ret;
}
};2875. 无限数组的最短子数组
题解：解法一：使用暴力解法模拟多个数组进行查找，可以通过target来确定至少需要多少个完整数组才有可能达到target，比如数组的总和是sum，模拟有(target/sum+1)+1个数组进行滑动窗口来查找是否又满足的区间；(target/sum+1)+1是完全足够包含所有情况的，可以思考一下为什么？？？
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
//通过滑动窗口实现
//先判断最少需要多少个nums
long long sum=0,n=nums.size();
for(auto e:nums) sum+=e;
int num=(target/sum+1)*2;
int ret=INT_MAX,left=0;
long long tmp=0;
for(int right=0;right<n*num;right++)
{
tmp+=nums[right%n];
while(tmp>target)
{
tmp-=nums[(left++)%n];
}
if(tmp==target) ret=min(ret,right-left+1);
}
return ret==INT_MAX?-1:ret;
}
};此解法简单，当时最后两个变态的测试用例是过不了的，超出时间限制。所以一下重点讲解方法二。
题解二：通过观察可以看出，如果target是比sum大的时候必定需要一个或多个完整的数组来实现，所以可以直接通过target/sum得到需要多少个完整的数组，此时再通过target%sum得到还需要多少个余数才能补全。该余数就可以只对两个数组合并进行滑动窗口看是否能够不全余数，注意此处需要的是两个数组进行合并而不是1个，可以思考下为什么？？？
class Solution {
public:
int minSizeSubarray(vector<int>& nums, int target) {
//通过滑动窗口实现
//先判断最少需要多少个nums
long long sum=0,n=nums.size();
for(auto e:nums) sum+=e;
int num=target/sum; //得到需要的完整nums个数
int more=target%sum; //得到需要部分nums的和
int ret=INT_MAX,left=0;
int tmp=0;
for(int right=0;right<n*2;right++) //进行滑动窗口
{
tmp+=nums[right%n];
while(tmp>more)
{
tmp-=nums[(left++)%n];
}
if(tmp==more) ret=min(ret,right-left+1);
}
return ret==INT_MAX?-1:ret+num*n;
}
};
76. 最小覆盖子串
题解：使用map+滑动窗口对字符进行计数，统计区间内各个种类字符数量是否满足。此题可能会出现超出内存限制的情况，所以可以适当的降低空间的使用，比如：将map改为使用char[128]的数组替代，或者不是存储返回值string ret，而是先存储其区间中的起始位置。
class Solution {
public:
string minWindow(string s, string t) {
//先通过map统计t总各个字符出现的次数，同时记录t中字符的种类
unordered_map<char ,int> mm;
for(auto e:t)
mm[e]++;
int n=s.size(),left=0,num=mm.size(); //num表示t中的字符种类，同于判断是否能更新答案
int ansl=0,ansr=0,flag=0; //使用flag来标记是否存在适合的字串
//进行滑动窗口
for(int right=0;right<n;right++)
{
if(mm.count(s[right]))
{
mm[s[right]]--;
if(mm[s[right]]==0) num--;
}
while(num==0)
{
if(ansr==0||ansr-ansl>right-left)
{
flag=1; //此处采用ansl和ansr的方式来代替string ret
//因为后面测试有很长的可能会出现超出内存限制
ansl=left,ansr=right;
}
if(mm.count(s[left]))
{
if(mm[s[left]]==0) num++;
mm[s[left]]++;
}
left++;
}
}
return flag==0?"":s.substr(ansl,ansr-ansl+1);
}
};632. 最小区间
解法一：暴力查找
解法一：使用滑动窗口，滑动窗口的区间从nums的最小值一直滑到nums的最大值位置。如何判断区间内的值至少包含数组中的一个元素？？？使用map对每个数组进行标记，再用一个vector来存储区间内每个数组的包含量即可。但是此方法毫无疑问会超时。
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
//使用滑动窗口进行解决，现根据数据确定滑动窗口的最大值和最小值
int minum=INT_MAX,maxum=INT_MIN;
int k=nums.size();
vector<unordered_map<int,int>> v(nums.size()); //统计每个nuums中的数据个数
for(int i=0;i<nums.size();i++)
{
if(nums[i].front()<minum) minum=nums[i].front();
if(nums[i].back()>maxum) maxum=nums[i].back();
for(auto e:nums[i]) v[i][e]++;
}
vector<int> count(nums.size(),0); //存储窗口中包含每一个数组的个数
int in=0,flag=0;
//从最大位置和中最小位置开始进行滑动窗口
int left=minum,ansl=minum,ansr=minum;
for(int right=minum;right<=maxum;right++)
{
//进行判断数字是否在k个数组里面
for(int i=0;i<k;i++)
{
if(v[i].count(right))
{
count[i]++;
if(count[i]==1) in++;
}
}
while(in==k)
{
if((ansr==minum&&flag==0)||ansr-ansl>right-left)
{
flag=1;
ansr=right,ansl=left; //更新窗口
}
for(int i=0;i<k;i++)
{
if(v[i].count(left))
{
count[i]--; //出窗口
if(count[i]==0) in--;
}
}
left++;
}
}
if(flag==0) return {};
else return {ansl,ansr};
}
};解法二：排序+滑窗
题解：将K个数组中的元素进行合并，再进行排序。通过滑动窗口来实现在一个区间中每个数组的元素都存在即可。找到区间中最右侧-最左侧的最小值。
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int k=nums.size();
vector<pair<int,int>> vv; //pair用于存储元素的值和对应的数组位置
for(int i=0;i<k;i++)
for(auto e:nums[i]) vv.push_back({e,i});
sort(vv.begin(),vv.end()); //进行排序
unordered_map<int,int> count; //存储每个数组元素出现的次数
int ansl=0,ansr=INT_MAX;
int n=vv.size(),left=0;
for(int right=0;right<n;right++)
{
count[vv[right].second]++; //入窗口
while(count.size()==k)
{
if(ansr-ansl>vv[right].first-vv[left].first)
ansr=vv[right].first,ansl=vv[left].first; //更新答案
if(--count[vv[left].second]==0) count.erase(vv[left].second);
left++;
}
}
return {ansl,ansr};
}
};解法三：堆
题解：使用堆进行实现，从第一个元素开始在K个数组中找最大值max和最小值min，此时的[max,min]就是一个有效的区间，但是不一定是最小区间，所以要进行缩减区间，将min替换成min所在数组的下一个元素来达到缩小区间的目的(也可能不会出现区间缩小的效果，但是并不影响)，持续进行直到一个数组走到最后一个位置时停止即可。
细节：使用优先级队列来实现每次获取最小值，方便每次删除最小值及拿去下一个位置元素，此处需要同时存储元素值，元素所在数组，在该数组位置。所以采用tuple作为基本单元。
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int n=nums.size();
int ansl=0,ansr=INT_MAX;
//优先级队列使用tuple作为基本单位，
//因为既要存储最小值，还要存储所在的数组，以及在数组的对应下标位置
priority_queue<tuple<int,int,int> ,vector<tuple<int ,int ,int>> ,greater<>> pq;
int themax=INT_MIN; //存储最大值
//进行下标为0的插入
for(int i=0;i<n;i++)
{
int tmp=nums[i][0];
if(tmp>themax) themax=tmp;
pq.push({tmp,i,0});
}
//进行遍历
while(1)
{
//堆顶就是最小值
auto [a,b,c]=pq.top(); //a表示最小值，b表示最小值所在的数组，c表示所在数组对应的下标
pq.pop();
//更新答案
if(ansr-ansl>themax-a)
ansl=a,ansr=themax;
if(c+1==nums[b].size()) break; //已经没有元素可以继续进行插入了,直接停止
int next=nums[b][c+1]; //插入下一个元素
pq.push({next,b,c+1});
themax=max(themax,next); //下一个位置可能是最大值
}
return {ansl,ansr};
}
};求子数组个数
越长越合法
2537. 统计好子数组的数目
题解：此处需要进行简单统计和转化，当一个数组恰好满足情况，则向该数组中增加left之前的元素仍然满足条件，所以仍然可以转化为越长越合法的模型。
class Solution {
public:
long long countGood(vector<int>& nums, int k) {
//求临界区间：有k对满足情况
unordered_map<int,int> mm;
int n=nums.size();
int left=0,differ=0;
long long ret=0;
for(int right=0;right<n;right++)
{
differ+=mm[nums[right]]; //统计该元素插入后新的子数组
mm[nums[right]]++; //入窗口
while(differ>=k)
{
mm[nums[left]]--; //出窗口
differ-=mm[nums[left]];
left++;
}
//此时恰好不满足
ret+=left; //更新答案
}
return ret;
}
};3298. 统计重新排列后包含另一个字符串的子字符串数目 II
题解：依旧是采用滑动窗口找恰好满足的情况。
class Solution {
public:
long long validSubstringCount(string word1, string word2) {
//仍然是越长越合法的模型，只需要统计word1区间中字符出现的次数即可
int ch[128]={0};
int count=0; //count用于存储字符的种类
for(auto e:word2)
{
if(ch[e]==0) count++;
ch[e]++;
}
int n=word1.size();
int left=0,k=0; //k用于存储满足的字符个数
long long ret=0;
int hash[128]={0}; //hash用于存储word1的各个字符个数
for(int right=0;right<n;right++)
{
hash[word1[right]]++; //入窗口
if(hash[word1[right]]==ch[word1[right]]) k++;
while(k==count)
{
if(hash[word1[left]]==ch[word1[left]]) k--; //出窗口
hash[word1[left++]]--;
}
ret+=left; //更新答案
}
return ret;
}
};越短越合法
2762. 不间断子数组
题解：根据题目可知区间中最多有3中不同的数；使用map+滑动窗口，使用map是因为map可以直接得到区间中最大值和最小值数据 ，将数据与和最大值和最小值进行比较即可。
class Solution {
public:
long long continuousSubarrays(vector<int>& nums) {
//因为0<=|nums[i1]-nums[i2]|<=2对于数组中每一段都成立，所以区间内最多有3个不同的数
map<int ,int> mm; //此处采用map因为我们希望直接拿出来最大值和最小值，
//使用unordered_map不能实现，使用map.begin()和map.rbegin()可以实现
int n=nums.size(),left=0;
long long ret=0;
for(int right=0;right<n;right++)
{
mm[nums[right]]++; //入窗口
while(mm.rbegin()->first-mm.begin()->first>2) //拿出最大值和最小值进行比较
{
if(--mm[nums[left]]==0) mm.erase(nums[left]);
left++; //出窗口
}
ret+=right-left+1; //更新答案
}
return ret;
}
};加餐
825. 适龄的朋友
题解：此题的关键在于对题目信息进行转化，根据题目要求可以得到x要和y发好友请求要满足：0.5*x+7<y<=x。所以当x越大的时候y就要求越大，而y一直是在x之前的，所以可以先对数组进行排序，再使用滑动窗口控制[left，right]，left表示y，right表示x即可。
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
//由题意知道，发送给y需要满足的条件是：0.5*x+7<y<=x即可，因为y<=x则第三个条件必定不会成立
//x越大y就越大，所以可以使用滑动窗口一个区间中可以发送请求的个数来记录解决
int hash[121]={0}; //使用hash对ages进行排序使得后面的x和y都是线性递增的
for(auto e:ages) hash[e]++;
int ret=0,left=0,tmp=0; //使用tmp来记录[left，right]之间的人数
for(int right=0;right<121;right++)
{
tmp+=hash[right]; //入窗口
while(2*left<=right+14) //确定满足0.5*x+7<y时y的位置，
tmp-=hash[left++]; //如果不满足就进行出窗口让left++，来找更大的y
if(left<=right) //判断y<=x的条件时候满足
ret+=(tmp-1)*hash[right]; //更新窗口
}
return ret;
}
};1156. 单字符重复子串的最大长度
题解：通过从其他位置交换字符使得形成更大的重复字符串；所以可以先找到一个不同的字符，将字符左右两边的重复字符进行统计来得到最长的长度。注意：交换来的字符是否又被区间统计进去。此处建议使用while循环，因为right并不是一直向后走的。
class Solution {
public:
int maxRepOpt1(string text) {
//此题可以通过交换字符使得相同子串更长
unordered_map<char,int> mm; //存储每一个字符出现的次数
for(auto e:text) mm[e]++;
int n=text.size();
int left=0,ret=0,right=0;
while(right<n)
{
while(right<n&&text[left]==text[right]) right++; //求左半边相同的数
int other=right+1; //从other开始进行右半边的查找
while(other<n&&text[left]==text[other]) other++; //求右半边相同的数
ret=max(ret,min(other-left,mm[text[left]]));
//min(other-left,mm[text[left]])保证通过其他位置字符进行交换使得连续时，
// 交换的位置没有计数没有重复
left=right; //从不同字符的位置开始进行查找
}
return ret;
}
};424. 替换后的最长重复字符
题解：通过将区间中不同的字符控制在K以内即可。控制区间[left,right]，定义maxcount记录区间中出现次数最多的重复字符个数，right-left+1-maxcount就是不同的个数。此题的难点在于对于maxcount的修改方面。此处maxcount<=ret<=maxcount+k，此处的ret是答案，因此我们只需要找到maxcount的最大值即可，所以对maxcount的维护只有maxcount=max(maxcount，mm[right])上，当left向右使区间缩小的时候就算是当前区间中maxcount减小了，我们也不需要进行调整，因为maxcount缩小后得到的答案也不会被更新使用；只有在maxcount增大时更新的答案才会被使用。
class Solution {
public:
int characterReplacement(string s, int k) {
//此题就是找一个最大区间，该区间内不同的字符不能超过k个
unordered_map<char ,int> mm; //存储区间中字符的种类和个数
int left=0,n=s.size();
int ret=0,right,maxcount=0; //用maxcount来记录区间中最长重复字符的个数
for(int right=0;right<n;right++)
{
mm[s[right]]++;
maxcount=max(maxcount,mm[s[right]]); //此处的maxcount只需要在此处进行维护即可
while(right-left+1-maxcount>k) //使用right-left-1来表示区间的长度，
{ //而right-left+1-maxcount来表示区间中要被替代的个数
if(--mm[s[left]]==0) mm.erase(s[left]);
left++;
}
ret=max(ret,right-left+1);
}
return ret;
}
};