滑動窗口簡介??

滑動窗口就是利用單調性，配合同向雙指針來優化暴力枚舉的一種算法。?

?該算法主要有四個步驟

1. 先進進窗口

2. 判斷條件，后續根據條件來判斷是出窗口還是進窗口

3. 出窗口

4.更新結果，更新結果這個步驟是不確定的，應題目要求判斷是在進窗口前更新結果還是出窗口前更新結果。

1. 長度最小的子數組

題目鏈接：209. 長度最小的子數組 - 力扣（LeetCode）

題目細節信息：

1.數組中都是正數? ?2.在數組中找到長度最小的子數組且子數組中的元素和小于target值?

解法：滑動窗口

我們先定義一個left指針和right指針，left和right之間就是一個窗口。在定義一個變量sum來記錄[left,right]區間的和。

根據題目要求，我們先確定第一個sum大于等于target值得右邊界，所以我們先讓right不斷進窗口。

以題目中的實例1為例

接著我們根據sum的值來判斷是否進窗口還是出窗口。sum的值無非會遇到兩種情況。

當sum小于等于target的時候，我們先要更新最小長度和sum的值，接著在進窗口，即讓left++?

如下圖：?

之前left指向的元素已經不在窗口里面了，這也是理解出窗口的一個圖解。

當sum小于target時，我們進窗口進行了，即right++?

滑動窗口的正確性

為什么能判斷滑動窗口是對的呢？

因為數組中的數據都是正數，當right找到第一個邊界使sum大于等于target的值時，我們就沒必要讓right繼續向后走了，因為數組中都是正數，right繼續走下去，sum會變大，但是len也會變長，此時len肯定就不是我們要的結果了。所以不讓right向后走，就避免了其他不符合題意情況的枚舉了。?

代碼實現

代碼一：我寫的形式

    public int minSubArrayLen(int target, int[] nums) {int n=nums.length;int left=0,right=0;int ret=Integer.MAX_VALUE;int sum=nums[right];while(right<n){if(sum<target){right++;//進窗口if(right<n){sum+=nums[right];}}else{ret=Math.min(ret,right-left+1);//更新長度最小值sum-=nums[left];//更新sum值left++;//出窗口}}return ret==Integer.MAX_VALUE?0:ret;}

代碼二：

    public int minSubArrayLen(int target, int[] nums) {int n=nums.length;int len=Integer.MAX_VALUE;int sum=0;for(int left=0,right=0;right<n;right++){//進窗口sum+=nums[right];while(sum>=target){//這里要用while循環len=Math.min(len,right-left+1);//更新最小長度sum-=nums[left];//更新sum的值left++;//出窗口}}return len==Integer.MAX_VALUE?0:len;}

2.無重復字符的最長字串?

題目鏈接：3. 無重復字符的最長子串 - 力扣（LeetCode）?

題目解析：在字符串中找到一個連續且無重復字符的子字符串，并返回其長度。

解法一：暴力枚舉(會超時)

枚舉從字符串的第一個字符開始往后，無重復字符的子串可以到什么位置，找出一個最大長度的即可。

因此，我們可以通過一個哈希表來記錄往后枚舉的過程中，字符是否出現重復的情況。

//時間復雜度O(n^2)
//空間復雜度O(1)
import java.util.*;
class Solution {public int lengthOfLongestSubstring(String s) {int len = s.length();int ret = 0;for(int i = 0; i < len; i++) {int[] hash = new int[128];for(int j = i; j < len; j++) {hash[s.charAt(j)]++;if(hash[s.charAt(j)] > 1) {break;}ret = Math.max(ret, j - i + 1);}}return ret;}
}

解法二：滑動窗口

此時，我們可以通過滑動窗口來優化上面的暴力枚舉。

首先，先通過一種枚舉的情況來分析，如下圖

當我們枚舉時，當right遇到第一個重復的字符a時，我們就不必要讓right繼續往后走了，因為前面的left的位置沒變，當right繼續往后走，left和right之間是一定有重復的字符的。

所以，此時，我們可以讓right先固定在原地，先讓left指針往后走，直到left指針跳過重復的字符，right才能繼續完后走。

但是，當left往后走的時候，right沒必要往回退到和left一樣的位置，因為當left沒有跳過第一個重復的字符時，right撐死只能走到第二個a的位置，且left往后走了，此時子串的長度肯定是比left沒有往后走時短的。

兩個指針沒有回退，這時就可以使用滑動窗口了。

這里先解釋下上面的hash數組的意思

這里hash數組的下標為字符串中字符的ASCII值，hash數組中的數據是該字符的出現次數。?

滑動川口的解題步驟：

1.進窗口：讓字符進入hash表中

2.判斷和出窗口：判斷該字符是否重復出現，如果重復出現，則出窗口，即將該字符從hash表中刪除。

3.更新結果：這里是先進行判斷后，才執行更新的操作。

代碼實現：

時間復雜度：O(n)
空間復雜度：O(n)public int lengthOfLongestSubstring(String ss) {int n=ss.length();char[] s=ss.toCharArray();int[] hash=new int[128];int left=0,right=0,ret=0;while(right<n){hash[s[right]]++;//進窗口while(hash[s[right]]>1){//判斷字符是否重復出現hash[s[left++]]--;//出窗口}ret=Math.max(ret,right-left+1);//更新結果right++;}return ret;        }

3. 最大連續1的個數

題目鏈接：1004. 最大連續1的個數 III - 力扣（LeetCode）

題目解析：最多可以將數組中的k個0翻轉為1，返回數組經過翻轉后，數組中連續1的最大個數。

雖然題目中是要求我們翻轉0，但是如果我們遇到0就將其翻轉為1的話，接著進行新的枚舉的時候，就又要將翻轉過的0，重新翻轉為0，此時，代碼就會很難寫，且很復雜。

其實，我們可以轉換為求區間的長度，只要該區間的0的個數沒有大于k個就行了。

解法一：暴力枚舉+zero計數器

定義一個left和right指針，我們可以讓left為起點向后枚舉，定義一個zero變量來保存枚舉過程中遇到0的個數?，如果zero的值大于k，此時我們就可以讓right指針停在該位置了，因為此時right如果繼續走下去，left和right區間就是不符合題目要求了。

也就是說，此時以left為起點的枚舉，得到的連續1的長度就是一個最優解了，此時就可以更新結果

所以，我們要換一個起點進行枚舉，既讓left++，接著讓right回到left的位置，以新的left為起點繼續，right繼續向后枚舉，重復上面的步驟。

解法二：滑動窗口

再暴力枚舉上進一步優化，當我們讓left++的時候，沒必要將right重新指向left的位置，因為當zero的值大于k時，right撐死也時只能走到剛才停止的位置，只有我們left跳過一個0的時候，讓zero減一，讓zero的值小于k時，此時right才可以繼續完后枚舉。

此時，發現，left和right指針是同向運行，且不會退，我們就可以使用滑動窗口算法來解決該問題。

步驟一：進窗口

當right完后枚舉時，遇到1就忽略，如果遇到0，就讓zero的值加1

步驟二：判斷+出窗口

當zero的值大于k時，我們就出窗口，也就時讓left++，如果left遇到1就忽略，如果遇到0，就

讓zero的值減1

步驟三：更新結果

此時，更新結果的步驟是在判斷的步驟之后。?

代碼實現：

//時間復雜度：O(n)
//空間復雜度：O(1) public int longestOnes(int[] nums, int k) {int left=0,right=0,zero=0;int n=nums.length;int ret=0;while(right<n){if(nums[right]==1){right++;}else{right++;zero++;//出窗口}while(zero>k){//判斷if(nums[left]==0){zero--;//進窗口}left++;}ret=Math.max(ret,right-left);//更新結果}return ret;}

注意：這里更新結果為什么不是right-left+1呢？因為我是再right++之后再更新長度，而不是再right++之前更新長度。?

更簡練版本：

    public int longestOnes(int[] nums, int k) {int ret = 0;for(int left = 0, right = 0, zero = 0; right < nums.length; right++){if(nums[right] == 0) zero++; // 進窗?while(zero > k) // 判斷if(nums[left++] == 0) zero--; // 出窗?ret = Math.max(ret, right - left + 1); // 更新結果}return ret;}

這個版本就是再right++之前更新長度，所以更新長度時是right-left+1?

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

題目鏈接：1658. 將 x 減到 0 的最小操作數 - 力扣（LeetCode）

題目解析：

1.我們每次進行一次刪減操作時，我們都要將數組最左邊或最右邊的元素刪去，供下一次刪減操作時使用

2.數組里面的都是正數

在該題中，只有數組里面全是正數，我們才能使用滑動窗口解決

分析：因為當數組里面有負數或者為0的數據時，當right到達第一個停止的位置時，當我們的tmp減去一個負數或者數據為0的數時，由于負數或0的緣故，會導致[left，right]區間的和有可能是等于或大于tmp的，所以，此時進行新的枚舉時，right有可能會向前退，也有可能繼續向后退。?

解題思路轉換：解決該題的時候，我們有時候會刪去最左邊的元素，有時候會刪去最右邊的元素，但是這種情況太復雜了，我們要轉換思路。

正難則反：

題目要求我們找到數組兩邊使x值減為0的最小個數，我們就可以轉換為求中間和為sum-x的最長子串。

解法一：暴力枚舉

套兩層for循環，遍歷每一個子數組的情況，根據子數組的和是否等于target的值，我們就更新結果，接著break跳出一層循環。

解法二：滑動窗口

我們通過滑動窗口來優化枚舉，我們每進行一次新的遍歷的時候，我們發現沒必要每次都讓right回到left的位置，因為數組里面都是正數，當left++之后，[left，right]區間的和肯定是小于target的。

此時，發現left和right指針都不回退，此時就可以使用滑動窗口。

1.進窗口：tmp+=nums[right]

2.判斷+出窗口：判斷tmp的值是否大于target，如果大于出窗口，即nums-=nums[left++]

3.更新結果：當tmp的值等于target的時候，我們就可以更新結果。

//時間復雜度：O(n)
//空間復雜度：O(1)public int minOperations(int[] nums, int x) {int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}int ret=-1;int target=sum-x;//處理細節，if(target<0) return -1;for(int left=0,right=0,tmp=0;right<nums.length;right++){tmp+=nums[right];//進窗口while(tmp>target){//判斷tmp-=nums[left++];//出窗口}if(tmp==target){ret=Math.max(ret,right-left+1);//更新結果}}if(ret==-1) return -1;//此時沒有找到子數組和為target的子數組else return nums.length-ret;}

?5.水果成籃（從這里開始比較認真）

題目連接：904. 水果成籃 - 力扣（LeetCode）?

題目分析：有一個fruit數組，在數組中，不同元素的值代表不同的水果種類，相同元素的值代表水果的種類相同，我們有兩個籃子，每個籃子只能裝一種水果，一個籃子中裝的水果數量沒有限制。如果摘水果的過程中，一旦遇到與籃子中水果種類不同的水果樹，就停止采摘，求這兩個籃子能裝的最大水果數量。?

以上可以總結為一句話：找一個連續的最長子數組，該子數組中的水果種類不超出兩種。?

解法一：暴力枚舉+哈希表?

我們可以將每一個子數組的情況枚舉出來，枚舉的過程中，我們可以借助一個hash表來保存枚舉過程中采摘水果的種類和數量。

我們用left為外層循環的標志，right為內層循環的標志

枚舉的小細節：

1. 為了防止在[1,2,1]的情況下，right指針會造成數組越界，所以我們每次進行一次內循環時，要對right指針進行判斷，是否越界。

2.當籃子中水果的種類也超出兩種時，也應該跳出該內層循環

3.在每一次采摘水果之前，必須判斷水果種類為2種時，下次采摘的水果是否為第三種水果，如果成立，則跳出內部循環

4.每次進行一次新的外部枚舉時，我們也要將hash表中上次枚舉保存水果的情況刪掉。

代碼

//空間復雜度:O(n)
//時間復雜度:O(n^2)public int totalFruit(int[] f) {Map<Integer, Integer> hash = new HashMap<Integer, Integer>();int ret = 0;for (int left = 0; left < f.length; left++) {for (int right = left; right < f.length; right++) {if (right == f.length || hash.size() > 2) {//判斷數組是否越界和水果種類的數量break;}int in = f[right];if (hash.size() == 2 && !hash.containsKey(in)) {//摘水果之前的判斷break;}hash.put(in, hash.getOrDefault(in, 0) + 1);ret = Math.max(ret, right - left + 1);}hash.clear();//在下次枚舉之前，刪除此次枚舉的情況}return ret;}

?解法二：滑動窗口

當我們進行新的left的枚舉時，我們沒必要讓right重新回到left的位置，因為當left進行新的枚舉時（left往后走），如果right重新返回到left指針的位置，往后枚舉的時候，right會出現兩種情況，第一種情況：right會停在在上一次left枚舉時，right的最后枚舉的位置或者超過right最后枚舉的位置。也就是說，以新的left為新的起點，進行right的枚舉時，right是一定會經過之前的枚舉停下的位置的，所以，我們就不必要將right返回到left的位置。

通過上面的分析，發現left和right指針是同向雙指針，這時我們就可以使用滑動窗口來解決這個問題。?

解題步驟

1.定義left=0，right=0

2.進窗口：讓hash[f[right]]++

3.判斷+出窗口（一個循環）：

? ? ? ? 當hash.size>2時，讓hash[f[left]]--，同時讓left++

4.更新長度?

用哈希表來實現:

//時間復雜度：O(n)
//空間復雜度：O(n)public int totalFruit(int[] f) {Map<Integer,Integer> hash=new HashMap<Integer,Integer>();int ret=0;for(int left=0,right=0;right<f.length;right++){int in=f[right];hash.put(in,hash.getOrDefault(in,0)+1);//進窗口while(hash.size()>2){//判斷int out=f[left];hash.put(out,hash.get(out)-1);//出窗口if(hash.get(out)==0){hash.remove(out);}left++;}ret=Math.max(ret,right-left+1);//更新長度}return ret;}

用數組來實現：?

    public int totalFruit(int[] f) {int n=f.length;int[] hash=new int[n+1];int ret=0;for(int left=0,right=0,kind=0;right<n;right++){int in=f[right];if(hash[in]==0){kind++;}hash[in]++;//進窗口while(kind>2){//判斷int out=f[left];hash[out]--;//出窗口if(hash[out]==0){kind--;}left++;}ret=Math.max(ret,right-left+1);//更新長度}return ret;}

?6.找出字符串中所有的異位字符串

題目鏈接：438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）?

題目解析：再s字符串中找出p字符串中的所有異位字符串

異位字符串就是相同字符但是字符的順序不一樣組成的字符串，如abc、acb、bac、bca、cab和cba都是abc的異位字符串。?

解決思路：滑動窗口+哈希表

如何判斷兩個字符串互為異位字符串呢？

第一種方法：我們可以將兩個字符串按字典的順序進行排序，接著判斷這兩個字符串是否相同就行，如果相同，那么就是異位字符串，如果不同，則不是異位字符串。

第二種方法：借用兩個哈希表，hash1來存儲p字符串，hash2來存儲s字符串，最終判斷兩個哈希表是否相同，如果相同，那么互為異位字符串，如果不同，則不是異位字符串。?

?以下圖為例

我們在s中找p的異位字符串，我們使用暴力枚舉時，第一次枚舉時，?當right-left+1長度為p.length()時，第一次枚舉就結束了，如下圖

此時第一次枚舉就結束了，進行第二次枚舉，讓left++，同時讓right返回到left的所處的位置

進行第二次枚舉時，right繼續走向right-left+1=p.length()的位置，此時發現right依然會進過之前的字符b和字符a

所以，每一次進行新的枚舉，沒必要讓right回到left的位置，這樣left和right都是同向雙指針，這時，我們就可以用滑動窗口來解決問題。

?進窗口：當right-left+1<=s.length時，hash2[in]++

?判斷+出窗口

? ? ? ? 如果right-left+1>p.length()，就出窗口，讓hash2[out]--，同時讓left++

更新結果

? ? ? ? 要判斷是異位字符串在更新結果

代碼實現

//時間復雜度：O(n+m)
//空間復雜度：O(n+m)public List<Integer> findAnagrams(String ss, String pp) {List<Integer> ret=new ArrayList<>();char[] s=ss.toCharArray();char[] p=pp.toCharArray();int[] hash1=new int[26];int[] hash2=new int[26];for(char ch:p){hash1[ch-'a']++;}for(int left=0,right=0;right<s.length;right++){char in=s[right];hash2[in-'a']++;//進窗口if(right-left+1>p.length){//判斷char out=s[left];hash2[out-'a']--;//出窗口left++;}//更新結果if(right-left+1==p.length){//判斷是否互為異位字符串boolean flag=true;for(int i=0;i<26;i++){if(hash1[i]!=hash2[i]){flag=false;}}if(flag==true)  ret.add(left);//更新結果}}return ret;}

進一步優化，此時我們可以在更新結果那里優化一下，因為在更新結果那里我們需要遍歷兩個哈希表，時間復雜度還是太大了，我們可以通過一個變量count統計窗口中的有效字符個數。

下圖解釋了什么是有效字符，一次類推?

前面我們用hash1統計了字符串p中的情況，用hash2統計了字符串s中的情況。

進窗口之后，我們對hash1[in]和hash2[in]進行比較，如果hash2[in]小于等于hash1[in]，那么此時就可以認為該字符是一個有效字符，讓count++

出窗口之前，我們對hash1[out]和hash2[out]進行比較，如果hash2[out]小于等于hash[out],此時就可以認為出去的字符是一個有效字符，讓count--

最終在更新結果的時候，我們只要判斷count是否等于p.length，如果等于p.length，就更新結果，如果不等于p.length，就不更新結果。

代碼實現

       public List<Integer> findAnagrams(String ss, String pp) {List<Integer> ret=new ArrayList<>();char[] s=ss.toCharArray();char[] p=pp.toCharArray();int[] hash1=new int[26];int[] hash2=new int[26];for(char ch:p){hash1[ch-'a']++;}for(int left=0,right=0,count=0;right<s.length;right++){char in=s[right];hash2[in-'a']++;//進窗口if(hash2[in-'a']<=hash1[in-'a']) count++;//更新有效字符個數if(right-left+1>p.length){//判斷char out=s[left];if(hash2[out-'a']<=hash1[out-'a']) count--;//更新有效字符個數hash2[out-'a']--;//出窗口left++;}//更新結果if(count==p.length) ret.add(left);}return ret;}

7.串聯所有單詞的子串?

題目鏈接：30. 串聯所有單詞的子串 - 力扣（LeetCode）?

?

我們如果將words的每一個字符串看成一個整體，在以這個整體為單位去在s中找串聯所有單詞的子串，這時就跟找異位字符串差不多了。如下圖

?

?這道題的思路和第6題的解題思路差不多，這里講不同點，假設words數組字符串的長度為m，數組的長度為len

1.right和left指針的位移

? ? ? ? right和left一次位移的長度為m

2.hash表的不同

? ? ? ? 這里的哈希表存的是字符串的種類和數量，即Hash<String,Integer>

3.進行滑動窗口的次數

? ? ? ? 次數為m次

這里對不同點3進行解釋

?

?代碼實現：

    public List<Integer> findSubstring(String s, String[] words) {Map<String,Integer> hash1=new HashMap<String,Integer>();//存儲wordsList<Integer> ret=new ArrayList<Integer>();for(String str:words){hash1.put(str,hash1.getOrDefault(str,0)+1);}int len=words[0].length(), m=words.length;for(int i=0;i<len;i++){//執行滑動窗口Map<String,Integer> hash2=new HashMap<String,Integer>();//存儲sfor(int left=i,right=i,count=0;right+len<=s.length();right+=len){String in=s.substring(right,right+len);hash2.put(in,hash2.getOrDefault(in,0)+1);if(hash2.get(in)<=hash1.getOrDefault(in,0)) count++;//判斷+出窗口while(right-left+1>m*len){String out=s.substring(left,left+len);if(hash2.get(out)<=hash1.getOrDefault(out,0)) count--;hash2.put(out,hash2.getOrDefault(out,0)-1);left+=len;}//更新結果if(count==m) ret.add(left);}}return ret;}

8.最小覆蓋子串?

題目鏈接：76. 最小覆蓋子串 - 力扣（LeetCode）?

?

題目分析：我們需要再字符串s中找一個子串，在這個子串中的字符種類，需要包含字符串t中所有字符類型，如果t中有了重復的字符，那么從s中找的子串的該字符的數量必須大于等于t中的重復字符的數量。

比如t為aba，那么在s中找的子串中，字符a的數量是不能小于t中a的字符數量。?

解題思路：

首先，我們還是想到暴力枚舉+hash表，我們將字符串中s的字符都枚舉一遍，在枚舉的過程中，如果遇到符合題目要求的子串，此時，就更新結果，接著立刻換一個字符進行新的枚舉，以此類推下去。

優化思路：滑動窗口

如下圖?

?

此時，我們需要讓left往后移動一步，當left++之后，left和right之間就會出現兩種情況。

第一種情況：

如果left++之后，left和right之間的字符種類沒有發生變化，當我們讓right回到left的位置，進行新的枚舉時，right還是會回到原來的位置。如下圖?

?

第二種情況：?

如果left++之后，left和right之間的字符種類發生變化，當我們讓right回到left的位置時，進行新的枚舉，為了找到新的符合題目要求的子串，此時right肯定時跑到原來位置的后面。如下圖：?

?

所以，我們發現沒必要每次都要將right返回到原來left的位置，我們只要根據每次left移動后的情況，根據情況來讓right不動或者往后移動。?

此時，發現left和right都是同向雙指針，此時就可以使用滑動窗口。?

在使用滑動窗口前，我們要用到兩個哈希表，一個用來存儲s字符串的情況，另一個用來存儲t字符串的情況。?

?進窗口：hash2[in]++

?判斷+更新結果+出窗口：

? ? ? ? 判斷：在s中找的子串是否符合題目要求，也就是hash2與hash1對應字符的數量是否一?樣

? ? ? ? 跟新結果：由于我們這里找到一個符合題目要求的子串就要跟新結果，所以此處的跟新結果實在出窗口之前

? ? ? ? 出窗口：hash2[out]--

在進一步優化：更新結果

在更新結果那里，我們需要遍歷兩個哈希表來判斷找的子串是否符合題目要求，每個哈希表都要遍歷一遍，時間復雜度還是太大了，此時，我們可以通過count變量來統計hash1和hash2中完全相同的字符數量。?

這里的完全相同是指數量和種類都相同。?

在進窗口之后，如果hash2[in]==hash1[in],那么，我們認為在in在hash1和hash2中是完全相同的字符，則讓count++

出窗口之前，如果如果hash2[in]==hash1[in],那么，我們認為在in在hash1和hash2中是完全相同的字符，則讓count--?

此時判斷條件就變為count==hash1.size().

代碼實現：

    public String minWindow(String ss, String tt) {char[] s=ss.toCharArray();char[] t=tt.toCharArray();int[] hash1=new int[128];//存儲tint[] hash2=new int[128];//存儲s;int kinds=0;//記錄t中有效字符的種類for(char ch:t){if(hash1[ch]==0) kinds++;hash1[ch]++;}int minlen=Integer.MAX_VALUE, begin=-1;for(int left=0,right=0,count=0;right<s.length;right++){//進窗口char in=s[right];hash2[in]++;if(hash2[in]==hash1[in]) count++;//判斷+更新+出窗口while(kinds==count){//更新結果if(right-left+1<minlen){minlen=right-left+1;begin=left;}//出窗口char out=s[left];if(hash2[out]==hash1[out]) count--;hash2[out]--;//出窗口left++;//維護窗口}}if(begin==-1) return new String();else return ss.substring(begin,begin+minlen);}