一起学算法（滑动窗口篇）

前言：

        对于滑动窗口，有长度固定的窗口，也有长度可变的窗口，一般是基于数组进行求解，对于一个数组中两个相邻的窗口，势必会有一大部分重叠，这部分重叠的内容是不需要重复计算的，所以我们可以通过相邻的窗口进行数据的延伸使用

1.固定窗口

1.定义

       如上图所示，两个相邻的长度为4的窗口（图中红色部分），下一个窗口一定比前一个窗口少一个数据，或者是多一个数据

       橘色为切换窗口时少的那个数据，黄色为切换窗口时多出来的那个数据，所以，可以直接沿用之前的数据，并且减去橙色的数据，加上黄色的数据，就是我们下一个窗口的值了，这就是滑动窗口的一个经典思路

2.例题解析：

给定一个数组num和两个整数k和target，请你返回长度为k且和大于target的子数组数目

    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;}

• 首先统计前k个数的sum，作为窗口的初始值，并且判断该子数组是否符合条件，符合则个数+1，不符合不用做操作
• 因为窗口时固定的，所以窗口左右端点同时向右移动，再次判断窗口中的数组是否满足条件，以O(1)的方式判断条件是否满足
• 最后返回计数器的值

2.可变窗口

可变窗口一般是使用双指针实现的，下面提供可变窗口的一个模板：

/* 滑动窗口算法框架 */
void slidingWindow(String s) {// 用合适的数据结构记录窗口中的数据HashMap<Character, Integer> window = new HashMap<>();//用合适的数据结构记录需要的数据int left = 0, right = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);window.put(c, window.getOrDefault(c, 0) + 1);// 增大窗口right++;// 进行窗口内数据的一系列更新...// 判断左侧窗口是否要收缩  计算窗口中特殊个数时，可能以个数为条件while (left < right && window needs shrink) {// d 是将移出窗口的字符char d = s.charAt(left);window.put(d, window.get(d) - 1);// 缩小窗口left++;// 进行窗口内数据的一系列更新...}}
}

leetcode题单：

删除元素后全为1的子数组

   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;}

最大的连续1的个数

    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的话，数值加1，为1的话，不用进行运算count+=1-nums[right];while(count>k){count-=1-nums[left++];}ans=Math.max(ans,right-left+1);}return ans;}

找到最长的半重复子字符串

public int longestSemiRepetitiveSubstring(String s) {char[] str = s.toCharArray();  // 将字符串转换为字符数组int left = 0;  // 左指针初始位置int same = 0;  // 记录当前连续相同字符的个数int max = 1;  // 记录最长的半重复子串长度for (int right = 1; right < str.length; right++) {if (str[right] == str[right - 1] && ++same > 1) {  // 发现连续相同字符序列left++;  // 将左指针向右移动一位while (left < right && same > 1) {if (str[left] == str[left - 1]) {  // 当前字符与前一个字符相同same--;  // 重置连续相同字符的个数continue;}left++;  // 将左指针向右移动一位}}max = Math.max(max, right - left + 1);  // 更新最长的半重复子串长度}return max;  // 返回最长的半重复子串长度
}

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

   public String minWindow(String s, String t) {//利用滑动茶窗口进行求解//记录需要的字符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;//窗口中满足需要字符的个数int vaild=0;int start=0;int len=Integer.MAX_VALUE;while(right<s.length()){//往窗口移进的字符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++;}//判断左侧窗口是否收缩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);}