【燒腦算法】定長滑動窗口：算法題中的“窗口”智慧

引言

定長滑動窗口習題剖析

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;} 
};