前言

滑動(dòng)窗口作為一個(gè)考點(diǎn)較高的算法，廣泛應(yīng)用于子串問題中，本文將進(jìn)行詳細(xì)講解。

一、滑動(dòng)窗口是什么

滑動(dòng)窗口是雙指針?biāo)惴ǖ囊环N，基本思路為維護(hù)一個(gè)窗口，然后從前往后遍歷元素進(jìn)行運(yùn)算。

二、滑動(dòng)窗口算法和其他雙指針?biāo)惴ǖ膮^(qū)別

雙指針?biāo)惴ǔＲ姷臑槿N：
1.快慢指針?biāo)惴?#xff08;常用于鏈表有環(huán)判斷）
2.雙向指針（兩個(gè)指針一個(gè)從最左，一個(gè)從最右出發(fā)進(jìn)行查找），典型應(yīng)用為二分查找
3.滑動(dòng)窗口（兩個(gè)指針一前一后出發(fā)，兩個(gè)指針中間維持一個(gè)窗口結(jié)構(gòu)

滑動(dòng)窗口代碼示例：

三、滑動(dòng)窗口原理講解

滑動(dòng)：說明窗口不是固定不變的，而是具有一定的可變性的

窗口：窗口并不是一定固定不變的，可以進(jìn)行擴(kuò)大，然后逐步進(jìn)行縮小直到滿足情況

我們在字符串 S 中使用雙指針中的左右指針技巧，初始化 left = right = 0，把索引閉區(qū)間 [left, right] 稱為一個(gè)「窗口」。

我們先不斷地增加 right 指針擴(kuò)大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

此時(shí)，我們停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時(shí)，每次增加 left，我們都要更新一輪結(jié)果。

重復(fù)第 2 和第 3 步，直到 right 到達(dá)字符串 S 的盡頭。

流程圖如下：

算法模版如下：

int left = 0, right = 0;while (right < s.size()) {// 增大窗口window.add(s[right]);right++;while (window needs shrink) {// 縮小窗口window.remove(s[left]);left++;}
}

四、例題講解

3.無重復(fù)字符的最長子串

代碼如下：

class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set =new HashSet<>();int max=0; //結(jié)果for(int right=0, left=0;right<s.length();right++){ //外層控制終點(diǎn) 也就是右邊指針char ch=s.charAt(right); //right 右指針指向的就是當(dāng)前需要考慮的元素while(set.contains(ch)){ //set中有重復(fù)元素 則縮短左邊界 同時(shí)從set集合出元素set.remove(s.charAt(left)); //這一步是關(guān)鍵left++;}set.add(ch); //將當(dāng)前元素加入max=Math.max(max,right-left+1); //計(jì)算當(dāng)前不重復(fù)子串的長度}return max;}
}

思路：
首先定義一個(gè)Set集合用來存儲(chǔ)當(dāng)前的字符，max變量來保存最長的子序列結(jié)果，然后就是滑動(dòng)窗口部分：
外層for循環(huán)控制終點(diǎn)，也就是right右指針， 里面一個(gè)while控制左指針，也就是左窗口，每當(dāng)右指針移動(dòng)一位時(shí)，取得當(dāng)前的字符，查看是否已經(jīng)添加到set集合中，如若沒有就添加，繼續(xù)移動(dòng)右指針，如若發(fā)現(xiàn)已經(jīng)存在，則移除該字符，將左指針向右移動(dòng)一位，每次移動(dòng)記錄當(dāng)前不重復(fù)子串長度，如若超過max值則賦值。

438. 找到字符串中所有字母異位詞

思路：
將P轉(zhuǎn)字符數(shù)組后排序成為判斷的key，然后采用滑動(dòng)窗口，定義左右指針，左指針指向s數(shù)組起始位置
右指針起始位置應(yīng)該是目標(biāo)p的長度-1，因?yàn)樽哟愇辉~肯定要和目標(biāo)的長度是一致的，然后開始進(jìn)行匹配，將子串同樣進(jìn)行排序轉(zhuǎn)成key，如果能匹配，則代表是異位詞，就將left左指針?biāo)饕砑拥浇Y(jié)果中，如果不能匹配，就不加，匹配一次后，左右指針同時(shí)++，確保長度都是和目標(biāo)字符長度一致。

代碼：

class Solution {public List<Integer> findAnagrams(String s, String p) {char [] arr=p.toCharArray(); //先將目標(biāo)字符串轉(zhuǎn)為字符數(shù)組后 排序 組成keyArrays.sort(arr);String key=new String(arr); //字符數(shù)組轉(zhuǎn)成keyHashSet<String> set=new HashSet<>();set.add(key); //將key添加進(jìn)去int length=p.length();char [] target=new char[length]; //需要比對的子字段 長度應(yīng)該和p的長度一致//   char [] strs=s.toCharArray();List<Integer> result=new ArrayList<>();for(int right=length-1,left=0;right<s.length();){ //外層循環(huán) 右指針 右窗口String   str =s.substring(left,right+1);// 減少移動(dòng)次數(shù) 每次需要匹配目標(biāo)字符對應(yīng)長度的窗口 注意substring 的endinx是不包括 所以要+1target=str.toCharArray();Arrays.sort(target); //此時(shí)得到當(dāng)前的 子串keyString son=new String(target);if(set.contains(son)){ //如果包含 則代表匹配 該子串是符合的異位詞result.add(left); //將左指針也就是子串的起始索引添加至結(jié)果}right++;left++;//左右指針同時(shí)+1；}return result;}
}