一、背景知識
- 滑動窗口算法（Sliding Window）：
- 在給定數組 / 字符串上維護一個固定長度或不定長度的窗口。可以對窗口進行滑動操作、縮放操作，以及維護最優解操作。
- 題型一：固定長度
- 題型二：不固定長度
?二、例題
1、無重復字符的最長子串（不定長度）
寫法一： 我的答案
class Solution {public int lengthOfLongestSubstring(String s) {if(s.length()==0){return 0;}int l=0;//左指針int r=0;//右指針int maxLen=1;List<Character> list=new ArrayList<>();while(r<s.length() && l<s.length()){if(!list.contains(s.charAt(r))){list.add(s.charAt(r));//窗口右側擴張maxLen=Math.max(maxLen,r-l+1);//維護一個子串長度的最大值r++;}else{int index=list.indexOf(s.charAt(r));//在窗口里查找被重復的字符的下標delItems(index,list);//把重復字符及其以前的字符移出窗口l=l+index+1;//窗口左側收縮}}return maxLen;}//public void delItems(int end,List list){while(end>=0){//從后往前刪list.remove(end);end--;}}
}
寫法二：?官方答案
外循環（for）枚舉字符串s的所有字符，當作滑動窗口的左邊界，進入內循環（while）后，不斷往右移，直到遇到重復的字符后，跳出內循環。
更新最長子串長度，刪除滑動窗口最左邊的一個元素。
如果該元素不是被重復的元素，就不會再次進入內循環，而是一直在外循環徘徊，一個接一個地刪掉滑動窗口最左邊的元素，直到刪掉那個被重復的元素
class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，記錄每個字符是否出現過，相當于滑動窗口Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指針，初始值為 -1，相當于我們在字符串的左邊界的左側，還沒有開始移動int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動一格，哈希集合移除一個字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不斷地移動右指針，哈希集合增加一個字符 occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 個字符是一個極長的無重復字符子串// rk-i+1為當前滑動窗口內的子串長度ans = Math.max(ans, rk - i + 1);}return ans;}
}
2、找到字符串中所有字母異位詞
該題用排序法會超時，用鏈表或哈希表會超出內存限制?
寫法一：
突破點：
在字符串 s中構造一個長度為與字符串 p的長度相同的滑動窗口，并在滑動中維護窗口中每種字母的數量；當窗口中每種字母的數量與字符串 p中每種字母的數量相同時，則說明當前窗口為字符串 p的異位詞。
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();//當字符串 s 的長度小于字符串 p 的長度時，字符串 s 中一定不存在字符串 p 的異位詞if (sLen < pLen) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] sCount = new int[26];//計算字符串s中26個字母出現的個數int[] pCount = new int[26];//計算字符串p中26個字母出現的個數for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a'];++pCount[p.charAt(i) - 'a'];}if (Arrays.equals(sCount, pCount)) {//兩個數組相等，找到異位詞ans.add(0);//記錄初始下標}//窗口開始滑動for (int i = 0; i < sLen - pLen; ++i) {//用滑動窗口遍歷字符串s--sCount[s.charAt(i) - 'a'];//滑動窗口左邊界收縮，sCount數組里該字母的個數減1++sCount[s.charAt(i + pLen) - 'a'];//滑動窗口右邊界擴張，sCount數組里該字母的個數加1if (Arrays.equals(sCount, pCount)) {//找到異位詞ans.add(i + 1);}}return ans;}
}
