前言：

? ? ? ? 對(duì)于滑動(dòng)窗口，有長度固定的窗口，也有長度可變的窗口，一般是基于數(shù)組進(jìn)行求解，對(duì)于一個(gè)數(shù)組中兩個(gè)相鄰的窗口，勢必會(huì)有一大部分重疊，這部分重疊的內(nèi)容是不需要重復(fù)計(jì)算的，所以我們可以通過相鄰的窗口進(jìn)行數(shù)據(jù)的延伸使用

1.固定窗口

1.定義

? ? ? ?如上圖所示，兩個(gè)相鄰的長度為4的窗口（圖中紅色部分），下一個(gè)窗口一定比前一個(gè)窗口少一個(gè)數(shù)據(jù)，或者是多一個(gè)數(shù)據(jù)

? ? ? ?橘色為切換窗口時(shí)少的那個(gè)數(shù)據(jù)，黃色為切換窗口時(shí)多出來的那個(gè)數(shù)據(jù)，所以，可以直接沿用之前的數(shù)據(jù)，并且減去橙色的數(shù)據(jù)，加上黃色的數(shù)據(jù)，就是我們下一個(gè)窗口的值了，這就是滑動(dòng)窗口的一個(gè)經(jīng)典思路

2.例題解析：

給定一個(gè)數(shù)組num和兩個(gè)整數(shù)k和target，請(qǐng)你返回長度為k且和大于target的子數(shù)組數(shù)目

    public int partitionString(int[] num,int k,int target) {if(num==null||num.length==0){return 0;}int sum=0;int i=0;for(;i<k;i++){sum+=num[i];}int count=0;if(sum>=target){count++;}for(int left=0;left<num.length;left++){sum-=num[left];sum+=num[++i];if(sum>=target){count++;}}return count;}

• 首先統(tǒng)計(jì)前k個(gè)數(shù)的sum，作為窗口的初始值，并且判斷該子數(shù)組是否符合條件，符合則個(gè)數(shù)+1，不符合不用做操作
• 因?yàn)榇翱跁r(shí)固定的，所以窗口左右端點(diǎn)同時(shí)向右移動(dòng)，再次判斷窗口中的數(shù)組是否滿足條件，以O(shè)(1)的方式判斷條件是否滿足
• 最后返回計(jì)數(shù)器的值

2.可變窗口

可變窗口一般是使用雙指針實(shí)現(xiàn)的，下面提供可變窗口的一個(gè)模板：

/* 滑動(dòng)窗口算法框架 */
void slidingWindow(String s) {// 用合適的數(shù)據(jù)結(jié)構(gòu)記錄窗口中的數(shù)據(jù)HashMap<Character, Integer> window = new HashMap<>();//用合適的數(shù)據(jù)結(jié)構(gòu)記錄需要的數(shù)據(jù)int left = 0, right = 0;while (right < s.length()) {// c 是將移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新...// 判斷左側(cè)窗口是否要收縮  計(jì)算窗口中特殊個(gè)數(shù)時(shí)，可能以個(gè)數(shù)為條件while (left < right && window needs shrink) {// d 是將移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 縮小窗口left++;// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新...}}
}

leetcode題單：

刪除元素后全為1的子數(shù)組

   public int longestSubarray(int[] nums) {int flag=0;int left=0;int mid=0;int max=0;for(int right=0;right<nums.length;right++) {if (nums[right] != 1) {flag++;if (flag > 1) {left = mid + 1;flag--;}mid = right;}max=Math.max(max,right-left);}return max;}

最大的連續(xù)1的個(gè)數(shù)

    public int longestOnes(int[] nums, int k) {if(nums==null||nums.length==0){return 0;}int left=0;int ans=0;int count=0;for (int right = 0; right <nums.length; right++) {//如果是為0的話，數(shù)值加1，為1的話，不用進(jìn)行運(yùn)算count+=1-nums[right];while(count>k){count-=1-nums[left++];}ans=Math.max(ans,right-left+1);}return ans;}

找到最長的半重復(fù)子字符串

public int longestSemiRepetitiveSubstring(String s) {char[] str = s.toCharArray();  // 將字符串轉(zhuǎn)換為字符數(shù)組int left = 0;  // 左指針初始位置int same = 0;  // 記錄當(dāng)前連續(xù)相同字符的個(gè)數(shù)int max = 1;  // 記錄最長的半重復(fù)子串長度for (int right = 1; right < str.length; right++) {if (str[right] == str[right - 1] && ++same > 1) {  // 發(fā)現(xiàn)連續(xù)相同字符序列l(wèi)eft++;  // 將左指針向右移動(dòng)一位while (left < right && same > 1) {if (str[left] == str[left - 1]) {  // 當(dāng)前字符與前一個(gè)字符相同same--;  // 重置連續(xù)相同字符的個(gè)數(shù)continue;}left++;  // 將左指針向右移動(dòng)一位}}max = Math.max(max, right - left + 1);  // 更新最長的半重復(fù)子串長度}return max;  // 返回最長的半重復(fù)子串長度
}

最小覆蓋子串(不固定窗口)

   public String minWindow(String s, String t) {//利用滑動(dòng)茶窗口進(jìn)行求解//記錄需要的字符Map<Character,Integer> need=new HashMap<>();//記錄窗口中所用的字符Map<Character,Integer>windows=new HashMap<>();for(char c:t.toCharArray()){need.put(c,need.getOrDefault(c,0)+1);}//作指針int left=0;//右指針int right=0;//窗口中滿足需要字符的個(gè)數(shù)int vaild=0;int start=0;int len=Integer.MAX_VALUE;while(right<s.length()){//往窗口移進(jìn)的字符char c=s.charAt(right);right++;if(need.containsKey(c)){windows.put(c,windows.getOrDefault(c,0)+1);if(windows.get(c).equals(need.get(c))){vaild++;}//判斷左側(cè)窗口是否收縮while(vaild==need.size()){//更新最小的覆蓋子串if(right-left<len){start=left;len=right-left;}//d是移出窗口的字符char d=s.charAt(left);left++;if(need.containsKey(d)){if(windows.get(d).equals(need.get(d))){vaild--;}windows.put(d,windows.get(d)-1);}}}}return len==Integer.MAX_VALUE?"":s.substring(start,start+len);}