現在來學習"滑動窗口"這一算法思想。
至于什么是"滑動窗口"呢？簡單來說就是同向雙指針；現在來通過題目來了解什么是"滑動窗口"
一、長度最小的子數組
題目鏈接：長度最小的子數組
題目解析
先來看題目，給了一個數組nums和一個整數target，讓我們找到nums的一個滿足條件（條件：子數組的和大于target）的最長子數組。
算法思路
首先第一次看到子數組/子串問題的算法題，能想到的思路就肯定是暴力枚舉了；現在就先來看暴力枚舉如何解決的。
暴力枚舉
我們依次枚舉整個數組的每一個子數組，并判斷是否滿足條件；滿足條件且長度小于最總結果，就更新最終結果。
上面意思呢？
暴力解法的大致思路如上述所示；現在來看一下暴力枚舉有哪些操作是不必要的
- 當
right第一次找到滿足條件的位置并更新結果后，left++，right從left位置再重新遍歷這個操作感覺有些多余了，因為我們
right遍歷時第一次遇到滿足條件的就停了下來；如果
right從left++后的位置開始再遍歷到上次滿足條件位置的位置，這一個遍歷過程很多余；
什么意思呢？
就以暴力枚舉中的示例來說：
right第一次遍歷到下標為3位置恰好滿足條件；此時區間是[0,3]，我們更新結果之后，left++
right從下標為1的位置開始再次遍歷；我們直到
[0,3]區間剛滿足條件，那區間[1,1]和[1,2]是一定不滿足條件的[1,3]才有可能滿足條件。
那這樣我們就可以想辦法省略這個不必要的步驟：
找到滿足條件的區間，并更新結果并lef++后，如何去解決right重新遍歷的問題？
解決問題，我們要找到問題的本質：
**暴力枚舉**中為什么要重新進行遍歷，本質問題就是我們不知道left++后，區間[left,right]的和；（所以暴力枚舉才會進行重新遍歷）
那我們現在定義一個變量
sum來實時記錄區間[left,right]的和，這樣不就不需要重新遍歷了嗎。我們只需要在
right向后遍歷和left更新時，順手更新一下sum的值就可以了。
滑動窗口
其實滑動窗口就是優化了暴力枚舉解法中不必要的部分
知道了如何去解決暴力枚舉中不必要的問題，現在來實現
通過上圖所示推到，我們的想法是可行的，現在來看整體的一個思路
滑動窗口，為什么稱為滑動窗口？
就是
right和left在遍歷更新的過程中維護了一段區間[left , right]，這個區間像窗口一樣在數組中滑動。
現在來看實現這個問題的一個整體思路：
- 進窗口：讓
right向右遍歷，更新區間[left , right]的和sum；稱為進窗口（就是讓right遍歷到的元素進入（窗口）區間內。- 出窗口：如果當前區間滿足條件（區間
和大于target)，就更新結果，然后讓left++，并更新區間[left , right]的和；重復上述操作直到區間不滿足條件。- 更新結果：至于什么時候更新結果，每一道題都不一樣，根據題目中的要求再決定什么時候更新結果。
代碼實現
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int ret = n+1;int l=0,r=0;int sum =0;while(l<n){//進窗口sum += nums[l++];//出窗口while(sum>=target){int x= l-r;if(x < ret)ret = x;sum-=nums[r++];}}if(ret == n+1)return 0;return ret;}
};
二、無重復字符的最長子串
題目鏈接：無重復字符的最長子串
題目解析
題目要求找出來給定字符串的所有子串中，不包含重復字符的最長子串；（也是子串問題）
s字符串中的字符由英文字母、數字、符號和空格組成。
算法思路
這里首先還是來看暴力解法
枚舉出來所有不包含重復字符的子串
在其中找到最長的然后返回。
這里先來看一下如何處理重復字符的問題：
這里可以使用一個
hash表，其中記錄每一個字符出現的次數；這樣使用
left和right雙指針遍歷的時候，遍歷到hash[s[right]] > 1就代表當前區間內存在重復字符。
當然這里所有數組來模擬hash就可以了。
現在來看使用滑動窗口如何去解決。
進窗口：首先
right向右遍歷，遍歷過程中hash[s[right]]++更新當前字符出現的次數；出窗口：當
hash[s[right]] >1時就表示當前區間不滿足條件，就要left++并且hash[s[left]]--更新區間內字符出現的字符；直到hash[s[right]]<=1。更新結果：這里每一次出完窗口就表示找到了一個滿足條件的區間，所以出完窗口之后更新結果即可。（這里在
right剛開始遍歷，每一次出完窗口，不一定會進入出窗口，但是也會更新結果，不會遺漏）。
代碼實現
這里寫代碼時注意，我們數組模擬hash，數組大概開辟128就差不多夠了。
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int n = s.size();int left = 0, right = 0;int ret = 0;while(right < n){//進窗口hash[s[right]]++;while(hash[s[right]]>1)hash[s[left++]]--;ret = max(ret,right-left+1);right++;}return ret;}
};
三、最大連續1的個數 III
題目鏈接：最大連續1的個數 III
題目解析
題目給定一個數組
nums，和k；其中nums中每一個數字不是1就是0。
k表示最多可以反轉（0變1）的次數。要求我們返回操作之后，數組中連續
1的最大個數。
什么意思呢？
就是我們最多可以將k個數組中的0變成1，然后我們要找出進行變換操作后數組中連續1的最大個數。
算法思路
這里，做出來本道題的關鍵就在于如何處理這個最多k次0變1的問題。
這里我們真的要將0變成1?
顯然是不可以的，這里數組有很多子數組，變了之后如何接著進行呢？
所以我們不能這樣操作，就只能另辟蹊徑：
這道題也是最長子數組問題，那也是要用滑動窗口的；我們想一想如何將其變成這樣的問題？
很顯然，這里題目要求最多可以進行
k次變換，我們不能進行真的變化操作。就只能在原數組中找到一個子數組（其中
0的個數不超過k）；
這樣這個問題就變成了我們熟悉的找子數組的問題，這里條件就是區間內0的個數不超過k。
所以思路就簡單明了了。
這里定義一個變量
zero來記錄區間[left , right]內0的個數。入窗口：
right向右遍歷，遇到0就更新zero。出窗口：如果
zero>k就表示當前區間內不滿足條件了，就進行出窗口操作；如果nums[left] == 0，就更新zero。更新結果：這里更新結果還是在出窗口之后，出窗口之后區間是滿足條件的并且每次入窗口之后不一定會出窗口，這樣更新就不會漏掉每一種情況。
代碼實現
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int left = 0, right =0;int zero = 0;int ret = 0;while(right<n){//入窗口if(nums[right++] == 0)zero++;//出窗口while(zero>k){if(nums[left++]==0)zero--;}//更新結果ret = max(ret,right - left);}return ret;}
};
這里第一次接觸到滑動窗口，感覺有一點點抽象；
這里滑動窗口其實就是同向雙指針，只是在遍歷的過程中維護了一段區間就像一個窗口一樣在數組中滑動。
實戰指南)
