目錄
1.長度最小的子數組
2.無重復字符的最長子串
3.將x減少到0的最小操作數
4.最大連續1的個數Ⅲ
5.找到字符串中所有字母異位詞
6.水果成籃
7.串聯所有單詞的子串
8.最小覆蓋子串
1.長度最小的子數組：209. 長度最小的子數組 - 力扣（LeetCode）中等
2.無重復字符的最長子串：3. 無重復字符的最長子串 - 力扣（LeetCode）中等
3.將x減少到0的最小操作數：1658. 將 x 減到 0 的最小操作數 - 力扣（LeetCode）中等
4.最大連續1的個數Ⅲ：1004. 最大連續1的個數 III - 力扣（LeetCode）中等
5.找到字符串中所有字母異位詞：438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）中等
6.水果成籃：904. 水果成籃 - 力扣（LeetCode）中等
7.串聯所有單詞的子串：30. 串聯所有單詞的子串 - 力扣（LeetCode）困難
8.最小覆蓋子串：76. 最小覆蓋子串 - 力扣（LeetCode）困難
滑動窗口。1.特點：具有單調性。2.步驟：進窗口、判斷窗口、出窗口。然后記錄結果在三個步驟其一
1.長度最小的子數組
（1）鏈接：209. 長度最小的子數組 - 力扣（LeetCode）中等
題意：找到一個最短的子數組（連續），要求子數組的和>=目標值。
（2）思路：滑動窗口不斷求和，當和>=目標值時，則判斷結果并出窗口
可以使用滑動窗口的原因是：數組元素都是正整數，不斷向右遞增時數組和是遞增的
（3）代碼
class Solution {public int minSubArrayLen(int target, int[] nums) {int ret = Integer.MAX_VALUE, sum = 0;for(int left=0,right=0;right<nums.length;right++) {sum += nums[right]; //1.進窗口while(sum >= target) { //2.判斷ret = Math.min(right-left+1,ret); //3.記錄結果sum -= nums[left++]; //4.出窗口}}return ret==Integer.MAX_VALUE?0:ret;}
}2.無重復字符的最長子串
（1）鏈接：3. 無重復字符的最長子串 - 力扣（LeetCode）中等
題意：找出沒有重復字符的最長子數組，也就是求最長子數組的長度
（2）思路：也是找子數組，所以可以使用滑動窗口。
如何判斷是否有重復元素，則可以遍歷窗口內元素即可
（3）代碼
class Solution {public int lengthOfLongestSubstring(String s) {//如何判斷窗口內是否有重復元素？？從窗口左邊開始遍歷，是否和新進入的窗口值相同//做法：始終保持窗口內的元素是不重復的int ret = 0;int n = s.length();for(int left=0,right=0;right<n;right++) {//1.入窗口--這里默認窗口為[left,right]的元素int cur = left;while(cur < right) { //2.判斷-窗口內是否有重復元素if(s.charAt(cur) == s.charAt(right)) {left = cur+1; //3.出窗口}cur++;}ret = Math.max(ret,right-left+1); //4.記錄結果-此時的窗口內保證無重復元素}return ret;}
}3.將x減少到0的最小操作數
（1）鏈接：1658. 將 x 減到 0 的最小操作數 - 力扣（LeetCode）中等
題意：每次從最左或者最右選取一個數（選取完默認從數組中刪除），要求和為x且長度最小的。這是正向的意思，我們反過來理解：在中間選取一段連續區間和為sum-x，要求長度最長
（2）思路：連續數組且都是正整數，且和為sum-x
（3）代碼
class Solution {public int minOperations(int[] nums, int x) {//題意：每次選擇最左邊或者最右邊的數，是否可以組合成x。//題意轉換：數組和為sum，是否存在這樣一個區間，使得和為sum-x的，要長度最大int sum = 0, n = nums.length;for(int i=0;i<n;i++) {sum += nums[i];}int target = sum - x, len = -1, path = 0;for(int left=0,right=0;right<n;right++) {path += nums[right]; //1.入窗口while(left < n && path > target) { //2. 判斷//3.出窗口path -= nums[left];left++;}//4.記錄結果if(path == target) len = Math.max(len,right-left+1);}return len==-1?-1:n-len;}
}4.最大連續1的個數Ⅲ
（1）鏈接：1004. 最大連續1的個數 III - 力扣（LeetCode）中等
題意：找出含有最多1的子數組，有k次機會可以將0變成1
（2）思路：連續子數組，可以使用滑動窗口。窗口內維護1的個數和將0變成1的次數
出窗口的條件：當0的個數大于K次時出窗口
（3）代碼
class Solution {public int longestOnes(int[] nums, int k) {//窗口內維護1，和可將0變成1的個數int n = nums.length;int ret = 0, count=0;for(int left=0,right=0;right<n;right++) {if(nums[right] == 0) count++; //1.入窗口while(count > k) { //2.判斷//3.出窗口if(nums[left] == 0) count--;left++;}//4.記錄結果ret = Math.max(ret,right-left+1);}return ret;}
}5.找到字符串中所有字母異位詞
（1）鏈接：438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）中等
題意：給兩個字符串，要求在s字符串中找出所有和p字符串互為異位詞的字符串
（2）思路：(窗口不斷向右移動，字母的數量是不斷增加的)窗口只需要維護p長度的大小即可，每次到達該長度，就判斷一下是否互為異位詞，判斷完記錄結果并出窗口。
用兩個計數數組判斷是否互為異位詞
（3）代碼
class Solution {public List<Integer> findAnagrams(String s, String p) {//如何判斷異位詞??int[] pMap = new int[26];for(int i=0;i<p.length();i++) {pMap[p.charAt(i)-97]++;}int[] sMap = new int[26];List<Integer> ret = new ArrayList<>();for(int left=0,right=0;right<s.length();right++) {//1.入窗口sMap[s.charAt(right)-97]++;//2.判斷if(right-left+1 == p.length()) {//3.判斷是否為異位詞boolean update = true;for(int i=0;i<26;i++) {if(sMap[i] != pMap[i]) {update = false;break;}}//4.記錄結果if(update) ret.add(left);//5.出窗口sMap[s.charAt(left++)-97]--;}}return ret;}
}6.水果成籃
（1）鏈接：904. 水果成籃 - 力扣（LeetCode）中等
題意：給一個數組，不同的值代表不同的水果。最多只能采摘兩種水果，求可以采摘的最多數量是多少？
（2）思路：不斷向右移動，數量增加，且是連續子數組。
每次入窗口判斷對應的map是否為空，為空則為不同的種類。當種類數大于2說明超出需要出窗口；最后記錄結果即可。
（3）代碼
class Solution {public int totalFruit(int[] fruits) {//如何判斷水果的種類和之前的相同或者不同？？可以用map記錄，如果=0則不同int[] map = new int[fruits.length];int ret = 0, kind = 0;for(int left = 0,right = 0; right < fruits.length; right++) {//1.入窗口并判斷水果種類是否增加if(map[fruits[right]] == 0) {kind++;}map[fruits[right]]++;//2.判斷-種類是否超出2種while(kind > 2) {//3.出窗口map[fruits[left++]]--;if(map[fruits[left-1]] == 0) kind--;}//4.記錄結果ret = Math.max(ret,right-left+1);}return ret;}
}7.串聯所有單詞的子串
（1）鏈接：30. 串聯所有單詞的子串 - 力扣（LeetCode）困難
題意：有一個字符串數組words，里面的字符串長度都相同，把它們以任何的順序組成一個字符串（單個單詞內部順序不變）。然后求該字符串在字符串s中出現的起始位置
（2）思路：把整個單詞看成一個字母，也就是找這些字母的異位詞出現的起始位置
1）先用Map存儲words中字符串出現的頻率
2）滑動窗口每次移動len步，每次進入窗口的單詞為right+len
3）進入窗口后，同時記錄map中，并判斷該單詞是否為有效單詞，如果有效則記錄count
4）如果count達到有效次數，則記錄結果
5）滑動窗口需要執行len次
（3）代碼：
class Solution {public List<Integer> findSubstring(String s, String[] words) {int n = words.length, len = words[0].length();Map<String,Integer> mapW = new HashMap<>(); //記錄words里面單詞出現的頻率for(String x : words) {mapW.put(x,mapW.getOrDefault(x,0)+1);}List<Integer> ret = new ArrayList<>();for(int k=0;k<len;k++) { //控制滑動窗口執行的次數Map<String,Integer> mapS = new HashMap<>(); //記錄窗口內里面單詞出現的頻率for(int left=k,right=k,count=0;right+len <= s.length();right+=len) {//每次進窗口為right+len, 用count記錄窗口內有效字符串的個數//1.進窗口String in = s.substring(right,right+len); //[right,right+len-1]mapS.put(in,mapS.getOrDefault(in,0)+1);//2.維護窗口內有效字符串個數if(mapS.get(in) <= mapW.getOrDefault(in,0)) count++; //如果in字符串在mapW也存在，且個數<=，說明是有效字符串//3.判斷if(right-left+1 > len * n) {String out = s.substring(left,left+len);if(mapS.get(out) <= mapW.getOrDefault(out,0)) count--; //如果out字符串在mapW也存在，且個數<=，說明是有效字符串//4.出窗口mapS.put(out,mapS.get(out)-1);left += len;}//5.記錄結果if(count == n) ret.add(left);}}return ret;}
}（*）不使用該計數數組，使用map如果做？
1）借助一個變量count統一窗口中有效“字符”的個數。這里的字符可能是單個字母，也可能是一個字符串。
2）進窗口時，判斷兩個hash中的字符個數，如果進窗口的hash個數小于原hash個數
8.最小覆蓋子串
（1）鏈接：76. 最小覆蓋子串 - 力扣（LeetCode）困難
題意：在字符串s中找出一個連續的子串，要求這個子串包含字符串t。并且要返回這個最短的子串
（2）思路：使用兩個哈希表或者計數數組，維護有效數字的窗口即可。
只需要記錄最短的長度和起始位置。
（3）代碼
使用Map接口：
class Solution {public String minWindow(String s, String t) {Map<Character,Integer> mapT = new HashMap<>();for(int i=0;i<t.length();i++) {char ch = t.charAt(i);mapT.put(ch,mapT.getOrDefault(ch,0)+1);}int minLen = Integer.MAX_VALUE, begin = -1;Map<Character,Integer> mapS = new HashMap<>();for(int left = 0,right = 0,count = 0;right < s.length();right++) {//1.入窗口char ch = s.charAt(right);mapS.put(ch,mapS.getOrDefault(ch,0)+1);//2.判斷是否有效if(mapS.get(ch) <= mapT.getOrDefault(ch,0)) count++;//3.維護窗口while(left <= right && count >= t.length()) {//4.記錄結果if(count == t.length() && minLen > right - left + 1) {begin = left;minLen = right - left + 1;}//5.出窗口char out = s.charAt(left);if(mapS.get(out) <= mapT.getOrDefault(out,0)) count--;mapS.put(out,mapS.get(out)-1);left++;} }if(begin == -1) return new String();else return s.substring(begin,begin+minLen);}
}使用數組模擬：
class Solution {public String minWindow(String ss, String tt) {char[] s = ss.toCharArray();char[] t = tt.toCharArray();int[] mapT = new int[128];//記錄第一輪mapint kinds = 0;for(int i = 0;i < t.length;i++) {if(mapT[t[i]] == 0) kinds++;mapT[t[i]]++;}int[] mapS = new int[128];int minlen = Integer.MAX_VALUE, begin = -1;for(int left=0,right=0,count=0;right<s.length;right++) {//1.入窗口char in = s[right];mapS[in]++;//2.判斷是否為有效種類if(mapS[in] == mapT[in]) count++;//3.循環while(count == kinds) {//4.記錄窗口if(right-left+1 < minlen) {begin = left;minlen = right-left+1;}//5.出窗口char out = s[left++];if(mapS[out] == mapT[out]) count--;mapS[out]--;}}if(begin == -1) return new String();else return ss.substring(begin,begin+minlen);}
}
 MyBatis-plus)
