【LeetCode】滑动窗口
坚持内卷
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
在right循环里，left++
我的做法：
class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0,right = 0, sub = 0,sum = 0,result = Integer.MAX_VALUE; for(right = 0;right <nums.length; right ++){ sum +=nums[right]; while(sum >= target){ sub = right -left +1; result = result < sub ?result :sub; sum -= nums[left++];} } return result == Integer.MAX_VALUE? 0 :result; }}不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是O(n)。
904. 水果成篮 中等题
这里有坑，数不大于数组的数量
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
class Solution { public int totalFruit(int[] fruits) { int left= 0,right = 0,count = 0; int [] i = new int[fruits.length]; int total = 0; if(fruits.length <=2){ return fruits.length; } for(right =0; right <fruits.length;right ++){ i[fruits[right]] +=1; if(i[fruits[right]] == 1) count++; while(count > 2){ //这里是while 而不是if i[fruits[left]] -=1; if(i[fruits[left]] == 0) count--; left++; } total = total >(right -left +1) ? total : (right -left +1); } return total; }}76. 最小覆盖子串
滑动窗口的思想：
用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。
步骤一
不断增加j使滑动窗口增大，直到窗口包含了T的所有元素
步骤二
不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
步骤三
让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。
class Solution { public String minWindow(String s, String t) { if(s =="" || s.length() == 0 || t == "" || t.length() == 0) return ""; int left = 0,right = 0, count = t.length(),size =Integer.MAX_VALUE,start =0; int [] need = new int[128]; for( int i = 0; i<t.length();i++){ need[t.charAt(i)] ++; } while(right <s.length()){ char c= s.charAt(right); if(need[c] >0){ count--; } need[c]--; if(count ==0){ while(left < right && need[s.charAt(left)] <0){ need[s.charAt(left)]++; left++; } if(size>(right -left +1)){ size = right-left +1; start = left; } need[s.charAt(left)]++; left++; count++; } right++; } return size ==Integer.MAX_VALUE ? "" :s.substring(start,start+size); }}