【烧脑算法】定长滑动窗口：算法题中的“窗口”智慧

引言

定长滑动窗口习题剖析

3439. 重新安排会议得到最多空余时间 I

2134. 最少交换次数来组合所有的 1 II

1297. 子串的最大出现次数

2653. 滑动子数组的美丽值

567. 字符串的排列

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

30. 串联所有单词的子串

220. 存在重复元素 III

总结

引言

本篇博客是继上一篇的续写，上一篇博客【入门算法】定长滑动窗口：算法题中的“窗口”智慧-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中找到，返回trueright++;}//出窗口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 longLL 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;} 
};