1.概念

所謂的滑動窗口，就是我們之前的雙指針的一個擴展應用，在上一章中，我們的雙指針是相向而行的，而這里的雙指針是同向而行的，由于其移動過程中像一個窗口一樣來回滑動，時大時小，而且還會來回動，因此我們給他起了一個名字：滑動窗口

2.使用場景

求給定數組的子數組時可能會用到，具體可以結合下文的示例來感受

3.例題

例1：長度最小的子數組

209. 長度最小的子數組 - 力扣（LeetCode）

這個題要求我們求找出該數組中滿足其總和大于等于?target?的長度最小的?子數組，符合滑動窗口的使用場景，下面我將具體闡述解題方法。

解題思路：

由于數組里面全是正數，并且是求和，因此我們可以利用一下單調性（肯定不會出現越加越小的情況），初始狀態下我們設置兩個指針left和right，并都指向下表為0的位置，并且假設left是左邊框，right是右邊框，設計一個求和的變量，right每次走的時候都自動計算一下當前的總和，并與target比較，如果小于target就繼續++，如果大于等于target就先計算一下長度，并且長度要和之前的長度值進行比較，取最小的，由于我們要去最小的length,所以我們可以讓left++，再求一下和（這里可以直接讓sum-=arr[left++])就好，之后不斷重復上述過程，直到找到最短的length位置。

參考代碼：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int left=0,right=0;int sum=0;int len=INT_MAX;for(int left=0,right=0;right<n;right++){sum+=nums[right];    //進窗口while(sum>=target)   //判斷{len=min(len,right-left+1);    //更新結果sum-=nums[left++];     //出窗口}}return len==INT_MAX?0:len;}
};

例2：無重復字符的最長字串?

3. 無重復字符的最長子串 - 力扣（LeetCode）

這道題要求我們尋找一個沒有重復字符的字串，而且字串是要連續的，那么我們還是兩種方法來解決這道題

解題思路：

方法一）暴力破解

將每個符合的子字符串都寫出來，分別求長度

方法二）滑動窗口

我們假設有這樣一個數組[ d e a b c a b c]，先設置兩個指針，left和right，之后讓right往后走（進窗口），與此同時，我們可以借用一下哈希表，由于哈希的本質就是映射，而題里面都是常見字符，為此我們可以用數組模擬哈希表，定義個hash[128]，哪個字符進去了，就在其映射的哈希表的位置上做上標記，完成這一步后，讓right一直往后走，直到right所對應的字符對應的映射在之前的哈希表中出現過為止，如上例中，left=0,right走到第二個a處停止，此后，由于我們的right已經給我們“趟過雷”了，此時將left在++到e的位置，right在從e開始走就多此一舉了，可以讓left直接++到第一個a后面的字符，也就是b,然后right繼續往前走就好，不斷重復上述過程，直到我們找到最優解為止。

參考代碼：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int left=0,right=0,n=s.size();int ret=0;while(right<n){hash[s[right]]++;    //將right位置的數映射到哈希表上，是我們的入窗口的操作while(hash[s[right]]>1){//這個位置之前被映射過了，證明當前的是重復的字符//出窗口，找到沒有映射的位置hash[s[left]]--;    //我們的left準備向右移動了，對應的映射也需要變化了left++;             //上例中，當left++到第一個b的時候，原來第一個a的映射就沒了，我們也就跳出循環了}ret=max(ret,right-left+1);        //更新結果right++;                         //讓下一個元素進入窗口}return ret;}
};

例3：翻轉數字（最大連續1）

1004. 最大連續1的個數 III - 力扣（LeetCode）

這道題題意很簡單，要求我們可以最多反轉K個0，之后找出最長的1的子字符串

解題思路：

這道題有一些小坑，如果直接考慮反轉，那可能有點麻煩了，我們不妨轉換一下題意，也就是說找一個字符串，其0的個數不超過K個就可以。這道題還是有兩種解題思路

法一）暴力枚舉+計數器

分別舉出每一段子字符串，并且0的個數要符合要求，之后找出最長的子字符串

法二）滑動窗口+計數器

我們可以仿照上一個題，定義兩個指針Left和right，以及一個計數器count,讓right不斷往右走，遇到零計數器就++，否則不觸發任何反應，繼續往右走（進窗口），當計數器達到k的時候（判斷條件），讓left也往左走（出窗口），1則不觸發任何反應，繼續往右走，0則計數器--，重復上述操作，直至right走到頭并且符合判斷條件

參考代碼：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret=0,left=0,count=0,right=0;for(right=0;right<nums.size();right++){//進窗口if(nums[right]==0){count++;}while(count>k){if(nums[left]==0){count--;}left++;}ret=max(ret,right-left+1);}return ret;}
};

例4：將 x 減到 0 的最小操作數?

1658. 將 x 減到 0 的最小操作數 - 力扣（LeetCode）

這道題給定我們一個數，并要求我們在數組內依次選一個數來減去x，直到x為0，如果存在則返回最小操作數，如果不存在則返回-1，這道題看起來貌似有一些困難，那我們應該怎么做呢？

解題思路：

想必大家都學過高數，在數學中，我們了解到正難則反，此題同理，我們只需要找到中間最長的子數組，并且其和target等于該數組元素總和減去x即可，這樣，我們便將題迎刃而解了

我們不妨設兩個指針left和right,以及和total,之后開始進窗口操作，即將Total增加，之后再判斷total與target的關系即可，如果大于，那么便出窗口，如果等于就更新結果，最后找最長的子數組就Ok,最后返回最小操作數

代碼示例：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int a:nums){sum+=a;}int target=sum-x;if(target<0){return -1;}int ret=-1;for(int left=0,right=0,total=0;right<nums.size();right++){total+=nums[right];while(total>target){total-=nums[left++];}if(total==target){ret=max(ret,right-left+1);}}if(ret==-1){return ret;}else{return nums.size()-ret;}}
};

?例4：水果成籃

904. 水果成籃 - 力扣（LeetCode）

這道題像是一個小的閱讀理解一樣，我們可以簡單分析一下，并借助注釋簡化一下題中的表達思想，最終，我們可能將題目簡化為在一個數組中找長度最長的子數組，并且里面只能由兩種數（水果種類），由此我們便可以開始解決這道題了

解題思路：

由于所有的解題思路都是由暴力解法演變而來的，所以我們在這里先講解一下暴力解法

方法一）暴力破解+哈希表

這種方法思路很簡單，就是從頭開始，挨個列舉出來子數組的長度，找到最大值后返回，那如何判斷此時的子數組達到最大值呢？我們這里可以借助哈希表，利用映射關系，當哈希表的長度等于2時，便達到了最大長度。如下圖所示

方法二）滑動窗口+哈希表

這種方法是基于暴力解法轉換而來的，當水果種類Kinds==2時，我們必然要移動左指針，這時就會出現兩種情況，一種是kinds減小，另一種是kinds不變，原因很簡單不解釋了，對于第一種情況，右指針不能動，對于第二種情況，右指針要右移，為此我們找到了這道題的破解點，滑動窗口。具體解法就是設置兩個指針，還是進窗口出窗口判斷等操作，對于進窗口操作，直接借助哈希表的映射，讓hash[f[right]]++,出窗口就是hash[f[left]]--，但是有一點值得注意的是我們還要記錄一下每種水果已經有了多少個，，并且最好還要有一個計數的，所以我們用hash<int,int>,也可以借助unordered_map來實現，有一個小細節就是我們希望減到0時就自動把這個水果給刪掉，以免影響水果種類的判斷，判斷條件就不多說了，就是hash.size()>2，我們就出窗口

代碼示例：

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int,int> hash;int ret=0;for(int left=0,right=0;right<fruits.size();right++){hash[fruits[right]]++;     //進窗口while(hash.size()>2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0){hash.erase(fruits[left]);}left++;}ret=max(ret,right-left+1);}return ret;}
};

這樣或許時間復雜度有點高，我們給改一下，由于題目給定了我們水果的個數，所以我們可以直接利用數組來模擬哈希表，只不過要再增加一個變量Kinds,相當于用空間換時間了。

改造后代碼：

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){//這里維護的是水果種類，不是個數，不能寫成進窗口就單純的kinds++，要看看之前有沒有這種 水果if(hash[fruits[right]]==0) kinds++;    //維護水果種類hash[fruits[right]]++;     //進窗口while(kinds>2){//出窗口hash[fruits[left]]--;if(hash[fruits[left]]==0){kinds--;}left++;}ret=max(ret,right-left+1);}return ret;}
};

改造完成！

例5：找字母異位詞

438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）

這道題要求我們在一個字符串中，找一個子字符串，要滿足字母組成上可以與給定字符串不同，但必須是由這幾個字符所構成，并返回第一個字符的索引。

解題思路：

題目既然要求我們找與給定字符串異位的子字符串，那么我的第一想法是利用哈希表，統計出給定字符串中每個字符出現的次數。之后我們在利用哈希表，并通過滑動窗口的方法，統計窗口里面的每一個字符出現的個數，這里為什么會聯想到滑動窗口呢？原因就是因為我們這兩個指針之間的距離是固定的，就是給定字符串的長度，right++必然就要left++，更像滑動窗口了，好我們回到問題本身，我們在統計窗口里面的每一個字符出現的個數之后，可以再設置一個計數器count,目的是記錄我們有效的字符，舉個例子，比如給定字符串由3個字符a,而我現在窗口里面又滑進來一個a,現在假設我們的總共在窗口里面又3個，那新進來的a就是有效字符，而換句話講，如果我現在窗口里面已經6個a了，那新來的這個a就沒啥用了，count就不需要++，如此一來，只需要我們的count與給定字符串的長度相等，那就證明符合異位，這就是我們需要的子字符串，出窗口同理，也要維護一下count

代碼實現：

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};      //統計字符串P中每個字符出現的個數for(auto e:p){hash1[e-'a']++;}int hash2[26]={0};      //統計窗口里面每個字符出現的個數int m=p.size();for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a']) count++;    //進窗口+維護countif(right-left+1>m)//判斷     要保證子字符串的長度{char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a']) count--;  //出窗口+維護count}//更新結果if(count==m) ret.push_back(left);}return ret;}
};

例6：串聯所有單詞的子串

30. 串聯所有單詞的子串 - 力扣（LeetCode）

這道題是我們上一道題的延申，我們可以將題目的意思翻譯一下，就是說在大字符串里面找小字符串，并且小字符串與word字符串是可以異位的

解題思路：

由于給定字符串中每個單詞的長度是一樣的，所以在這里我們可以將長字符串分割成幾個短字符串。在上述事例中，w有兩個三個字母的單詞組成。那么我們便可以將大字符串三個字符為一組分割成若干份，從頭開始畫，也許有人會問，萬一是從第二個字符開始它才是符合的，那應該怎么辦？這里邊要借助我們的滑動窗口來解決了。我們可以讓起始滑動的位置從左向右依次移動，當移動到第二個起始位置之時，及上述事例的字母f，此時我們便可以停止移動，因為再移動也是重復的沒有意義，那我們怎么確定f的位置呢？這里邊又要借用w中每個單詞的長度是相等的，可以求出單詞的長度，這樣就可以確定出f的位置。之后再利用哈希映射等方法可以破解此題，破解方法與上一題相似。

參考代碼：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;     //保存words里面所有單詞的頻次for(auto& e:words)  hash1[e]++;int len=words[0].size();        //求出一個單詞有幾個字符int m=words.size();      //求出有幾個單詞for(int i=0;i<len;i++)       //執行Len 次{unordered_map<string,int> hash2;    //維護窗口內單詞的頻次for(int left=i,right=i,count=0;right+len<=s.size();right+=len){//進窗口+維護 countstring in=s.substr(right,len);hash2[in]++;if(hash1.count(in)&&hash2[in]<=hash1[in])    //有效字符串count++;//判斷if(right-left+1>len*m){//出窗口+維護countstring out=s.substr(left,len);if(hash1.count(out)&&hash2[out]<=hash1[out])   //有效字符串count--;hash2[out]--;left+=len;}//更新結果// 如果當前窗口包含所有單詞，記錄起始索引if(count==m)ret.push_back(left);}}return ret;}
};

例7：最小覆蓋字串

76. 最小覆蓋子串 - 力扣（LeetCode）

這個題要求我們在一個字符串中找的一個最小字串，并且這個最小字串要包含給定的另一個字串，那么我們應該怎么做呢？

解題思路：

法一）暴力破解+哈希表

這道題基本思想和前面的差不多，我們第一種想法就是暴力破解，我們可以先遍歷字符串2，探明要尋找的字母類型和個數，并且可以將其映射在哈希表中，之后我們再一一例舉字符串1的所有符合題目條件的子字符串，并找出最小子字符串，完成本題

法二）滑動窗口+哈希表

我們還是遍歷字符串2，并將每個字符都入hash2

之后可以定義兩個指針left和right，之后讓right往后走，每次走之前都讓right所指元素入哈希表，當right入的是有效字符（即是hash2里面的字符）時，可以check(hash2,hash1),符合條件就更新結果，之后讓left++，可能還會有兩種結果，一種是符合要求，那我們的right就不用動，另一種是不符合要求，那我們的right就要++了，不斷重復上述操作，直至循環結束！

優化：

由于我們的每一次check的花銷都會很大，因為需要遍歷一下hash1和hash2,而且指針只要碰到一個有效字符就要check一下，那倘如字符串2里面有一萬個a,我們的字符串里面有兩萬個a，那我們的編譯器豈不是不用干別的了？因此，可以將上述代碼給出優化！

優化的方法也很簡單，我們可以定義一個變量count,用于標記有效字符的種類，并且在進窗口和出窗口時對其進行維護，具體來說就是在進窗口之后，當hash2[in]==hash[1]時count++，那為什么是=而不是>呢？原因就是=的時候就已經符合條件了，如果>的時候再去統計就會導致這個字符重復統計，并且也沒有必要，然后在出窗口之前，如果將要出去的字符符合hash2[out]==hahs1[out],那么我們的count就要--，之后我們的判斷條件就可以變為count==hash1.size()

參考代碼：

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};int kinds=0;     //統計有效字符有多少種int hash2[128]={0};for(auto e:t){if(hash1[e]==0){kinds++;}hash1[e]++;}int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in]){count++;}while(count==kinds){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left];left++;if(hash2[out]==hash1[out]){count--;}hash2[out]--;}}if(begin==-1){return "";}else{return s.substr(begin,minlen);}}
};

至此，滑動窗口篇章結束！！！

接下來的文章，將會為大家講解二分查找的算法！?