目录
引言
本篇博客是继上一篇的续写，上一篇博客【入门算法】定长滑动窗口：算法题中的“窗口”智慧-CSDN博客介绍了定长滑动窗口的使用场景及方法，以及一些常见的面试题型，本篇博客将对定长滑动窗口题型进行进一步深入，本章的题目有难度需要有一定的滑动窗口思想。
PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
定长滑动窗口习题剖析
3439. 重新安排会议得到最多空余时间 I
题解：重新安排k个会议，得到最大空余时间，不能调整会议的先后顺序。通过分析得到最大空余时间的方法是将k+1个会议移动到一起就能让空余最大，这也就能够转化为在一个只有k个会议的区间内最大空余时间问题。
class Solution {
public:
int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
//本题通过k次移动可以实现将k+1个会议进行整合，
//这也就实现了让k个会议左右两边的空余时间进行整合
//所以本题就转化为了求k个会议两边空余时间的最大值
//使用滑动窗口实现
int n=startTime.size();
int left=0,right=startTime[0]; //此处right要跳着走，不能使用right++，否则会超时
int ret=0,tmp=k,intime=0,i=0; //intime用来统计区间内会议的时长,i表示是第几个会议
while(i<n)
{
//入窗口
while(i<n&&tmp>=0)
{
if(startTime[i]==right&&tmp==0) break;
if(startTime[i]==right)
{
intime+=endTime[i]-startTime[i]; //统计区间内会议的时长
tmp--,i++; //对left和right区间内的会议个数进行统计
if(i==n) return max(ret,eventTime-left-intime);
right=startTime[i];
}
}
//更新答案
ret=max(ret,right-left-intime);
//出窗口
left = endTime[i - k]; //让left移动到区间内第一个会议结尾
intime -= (endTime[i - k] - startTime[i - k]); //此处减去区间内第一个会议时长
tmp++ ;
}
return ret;
}
};2134. 最少交换次数来组合所有的 1 II
题解：将数组中的所有1聚集起来，通过交换让一个区间内全部存储1，求最小的交换次数。找一个区间能够包含所有的1，且这一个区间内0的个数最少，这样交换的此处也就最少了。这一区间长度就是1的个数。通过滑动窗口进行处理，注意此题是环形数组要特别处理。
class Solution {
public:
int minSwaps(vector<int>& nums) {
//此题要求将数组中1都聚集起来，也就是说有一部分区域内都是1
//这也就使得只需要保持该区域中0的个数最小即可，这一个区域大小不难看出就是1的总个数
int n=nums.size(),one=0;
for(auto e:nums)
if(e==1) one++; //统计数组中1的个数
int left=0,right=0;
int ret=INT_MAX,tmp=0;
while(right<n+one) //right<n+one来处理泛型数组的要求
{
//入窗口
while(right-left<one)
if(nums[(right++)%n]==0) tmp++;
//更新答案
ret=min(ret,tmp);
//出窗口
if(nums[(left++)%n]==0) tmp--;
}
return ret;
}
};1297. 子串的最大出现次数
题解：字符串的范围是minSize---maxSize之间，出现最多的一定是子字符串，即最小长度的字符串，所以此处的最大值可以忽略。还是通过滑动窗口来解决。
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
//通过map来统计子字符串出现的次数
unordered_map<string, int> m;
int ch[26] = { 0 }; //统计字符的个数
int right = 0, left = 0, n = s.size();
int differ = 0; //用来统计不同字符的个数
int ret=0; //返回值
while (right < n)
{
//入窗口
if (ch[s[right] - 'a'] == 0) differ++;
ch[s[right++] - 'a']++;
if(right - left == minSize) //长度满足条件进一步判断是否满足条件
{
//调整答案
if(differ<=maxLetters)
{
string tmp=s.substr(left,right-left);
m[tmp]++;
ret=max(ret,m[tmp]);
}
//出窗口
ch[s[left] - 'a']--;
if (ch[s[left] - 'a'] == 0) differ--;
left++;
}
}
return ret;
}
};2653. 滑动子数组的美丽值
题解：此题分轻松的看出是一个滑动窗口问题，所以此题的关键在于怎么求第x小的数。采用优先级队列？？删除的时候不好操作；每次k个排一次序？？时间复杂度太高了。通过分析数据看到nums[i]大小在-50到50以内，所以可以采用计数排序的方法来解决。
class Solution {
public:
#define N 50
//求第x小的数
int GetMinK(int* count,int x)
{
for(int i=0;i<2*N+1;i++)
{
if(count[i]!=0) x-=count[i];
if(x<=0) return i;
}
return 0;
}
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
//此题的nums[i]的数据范围较小，所以可以通过计数排序的方法进行求第小的数
int count[2*N+1]={0};
//进行计数排序
int left=0,right=0,n=nums.size();
vector<int> ret;
while(right<n)
{
//入窗口
while(right-left<k)
count[nums[right++]+N]++;
//调整答案
int a=GetMinK(count,x)-50;
if(a<0) ret.push_back(a);
else ret.push_back(0);
//出窗口
count[nums[left++]+N]--;
}
return ret;
}
};567. 字符串的排列
题解：通过先遍历s1来确定s1中字符的种类及个数，若s2中有s1的子串，其区间长度必定是s1的长度，所以其窗口的长度确定，可直接使用滑动窗口。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int k=s1.size(),n=s2.size();
if(k>n) return false; //s1的长度小于s2，必定不成立
//通过一个长度为k的滑动窗口来实现,需要对s1的字符种类及个数进行计数来决定其是否是子串
int ch[26]={0}; //通过ch来记录s1字符的种类及个数
int num=0; //用num来记录s1有多少个不同的字符，方便判断s2的区间中是否是字串
for(auto e:s1)
{
if(ch[e-'a']==0) num++;
ch[e-'a']++;
}
int left=0,right=0;
while(right<n)
{
//入窗口
while(right<n&&right-left<k)
{
ch[s2[right]-'a']--;
if(ch[s2[right]-'a']==0) num--;
if(num==0) return true; //此时区间内所有的字符都能在s1中找到，返回true
right++;
}
//出窗口
if(ch[s2[left]-'a']==0) num++;
ch[s2[left]-'a']++;
left++;
}
return false;
}
};438. 找到字符串中所有字母异位词
题解：与上题相同，只需要将每次找到后将下标放入到数组中即可。
class Solution {
public:
vector<int> findAnagrams(string s2, string s1) {
int k=s1.size(),n=s2.size();
if(k>n) return {}; //s1的长度小于s2，必定没有满足条件的
//通过一个长度为k的滑动窗口来实现,需要对s1的字符种类及个数进行计数来决定其是否是子串
int ch[26]={0}; //通过ch来记录s1字符的种类及个数
int num=0; //用num来记录s1有多少个不同的字符，方便判断s2的区间中是否是字串
for(auto e:s1)
{
if(ch[e-'a']==0) num++;
ch[e-'a']++;
}
int left=0,right=0;
vector<int> ret;
while(right<n)
{
//入窗口
while(right<n&&right-left<k)
{
ch[s2[right]-'a']--;
if(ch[s2[right]-'a']==0) num--;
if(num==0) ret.push_back(left); //此时区间内所有的字符都能在s1中找到，将第一个位置的下标插入
right++;
}
//出窗口
if(ch[s2[left]-'a']==0) num++;
ch[s2[left]-'a']++;
left++;
}
return ret;
}
};30. 串联所有单词的子串
题解：与上一题类似，只不过将字符换位了判断字符串。此题依旧可以采用滑动窗口只不过从滑动字符变成了滑动字符串，用一个窗口维护每次需要统计的单词总数，每一次进---出都对单词进行操作即可。但是需要注意：第一个单词的起始位置不止有一个。
class Solution {
public:
//words中字符串给长度相同是重要信息
//先将words放入到set中去，方便判断子字符串是否满足条件
vector<int> findSubstring(string s, vector<string>& words) {
int num=words.size(),len=words[0].size(); //用num来表示有多少个子字符串，len表示每一个字符串长度
int n=s.size();
if(n<num*len) return {}; //s长度比words总长小直接返回
vector<int> ret;
for(int k=0;k<len;k++) //采用滑动窗口的方式进行，进单词--判断--出单词，要特别注意的是的第一个单词开始的位置
{
unordered_map<string,int> all; //int记录区间内单词与目标的单词个数差
for(auto e:words)
all[e]--;
int left=k,right=k;
//先将num-1个单词入窗口，因为在后面循环中每次入单词和出单词都是对一个单词进行操作
for(int i=0;i<num-1;i++)
{
if(right+len>n) break; //防止结尾处不能满足一个单词
string tmp=s.substr(right,len);
if(++all[tmp]==0) all.erase(tmp); //差为0，就从map中删除
right+=len;
}
while(right<n)
{
//进行入窗口,再入一个单词
if(right+len>n) break;
string tmp=s.substr(right,len);
if(++all[tmp]==0) all.erase(tmp);
right+=len;
//更新答案
if(all.empty()) ret.push_back(left);
//出窗口
tmp=s.substr(left,len);
if(--all[tmp]==0) all.erase(tmp);
left+=len;
}
}
return ret;
}
};220. 存在重复元素 III
题解：滑动窗口+二分查找。根据题目：两个下标i和j，abs(i - j) < indexDiff 就不难想到要使用滑动窗口解决。但是对于abs( nums[i] - nums[j] )<=valueDiff（可以拆分为 nums[i] - valueDiff<= nums[j] <=nums[i] + valueDiff）应该如何进行处理，可以遍历nums[i]将其前面的indexDiff个中找是否存在满足abs( nums[i] - nums[j] )<=valueDiff 的数据即可，可以使用set存放前面indexDiff个数据，然后找第一个 >=nums[i] - valueDiff的数据记为l，再判断abs(l+nums[i])<=value是否满足。
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
//使用 滑动窗口+二分
//控制一段长度小于indexDiff的区间，以nums[i]为基点看理他最近的数是否满足第二个条件
int left = 0, n = nums.size();
set<int> s;
for (int right = 0; right < n; right++)
{
auto l = s.lower_bound((long)nums[right]-valueDiff);
if ((l != s.end() && abs(*l - (long)nums[right]) <= valueDiff))
return true;
if (right - left == indexDiff)
s.erase(nums[left++]);
s.insert(nums[right]);
}
return false;
}
};
能否对上面代码进行优化？？？
此处采用一种新方法：桶排序
上述方法使用了一个循环+二分查找时间复杂度是O(N*logN))，查找时使用的时二分查找logN，能否对查找进行优化，优化为O(1)；O(1)的查找就要使用哈希桶了。
当前位置值如果时num，使用哈希桶去找[ num-valueDiff,num+valueDiff ]中的是否存在值，那么查找的时间复杂度就是O(valueDiff)了，当valueDiff很大的时候肯定不是O(1)的查找；
那就不能直接将一个数据放在一个桶中来实现，对数据进行分类，将一组数据放入桶中。abs(nums[i]-nums[j] )<=valueDiff所以可以将valueDiff看成一组，比如 valueDiff=3时 0 1 2 | 3 4 5 | 6 7 8 | 9 10 11将每3个数据看作一组，放入到一个桶中，当一个桶中有两个数据时这两个数据就满足条件，当该位置的桶没有数据但是旁边桶中有数据的时候，判断旁边桶的数据时候满足条件。但是valueDiff可能是0，在进行除法的时会出现汇报发错，所以不直接将valueDiff看作一组，而是将valueDiff+1看作一组。
计算哈希桶的key：对于>=0的数，实际 val/(valueDiff+1) 即可，但是对于负数来说-4 -3 -2 -1，如果直接对负数/(valueDiff+1)就会导致，-4和-3 -2 -1分成两组，所以对于负数要将数据+1再除，+1后-4 -3 -2 -1都映射到0上面，而0 1 2 3 也映射到0上面，所以还需要对结果 -1；
非负数的key：index= val / (valueDiff+1)；
负数的key：index= (val+1) / (valueDiff+1) -1。
class Solution {
#define LL long long
LL size; //用于计算当前数据放在哪一个桶里面
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
//使用哈希桶进行处理
size=valueDiff+1L; //1L指的是将1转化为long long类型
unordered_map<LL,LL> m; //作为存储数据的哈希桶
int left=0,n=nums.size();
for(int right=0;right<n;right++)
{
LL val=nums[right];
LL index=getIdx(val); //记录放在哪一个桶中
if(m.count(index)) return true;
LL l=index-1,r=index+1; //判断左右两个桶中的数据是否满足条件
if((m.count(l)&&abs(val-m[l])<=valueDiff)||(m.count(r)&&abs(val-m[r])<=valueDiff)) return true;
if(right-left>=indexDiff)
m.erase(getIdx(nums[left++]));
m.insert({index,val});
}
return false;
}
LL getIdx(LL u)
{
return u>=0?u/size:(u+1)/size-1;
}
};总结
此篇博客中的题目不再仅仅是简单的定长滑动窗口题目，更多的是需要进行一定的分析搭配其他的算法进行处理，此篇题目更注重一题多解，让我们再面试的时候可以灵活应变，找到最优解。题目不少，难度较高，感谢阅读！！！