滑动窗口 第一讲

某一类题做多了就发现其实里面都有固定的一个套路，在一个套路下在做不同的延伸。联想到其实人跟人的交往也是差不多，有一些固定的套路。比如一个人找你聊天，大概率那个人不在乎你说啥，ta只在乎ta要说啥。你这时候要确定一点，ta为啥找你说（ta是觉得你是一个可靠的朋友和聆听者 还是 一个情绪垃圾桶），你值不值得花时间听ta说（那你觉得ta是把你当垃圾桶，还是可靠的朋友）。而不是要怎么帮ta解决问题。 扯远了回到滑动窗口问题

套路1： i j 齐头并进，while循环处理条件。
题目：209， 713， 1004， 2024

209：题目要求，找到最小连续subarray，这个subarray的和刚好是target。
那么看到连续的subarray 基本上就可以嘴角上扬了。这就是一个典型的滑窗问题。

思路：
1. 找最小那么就需要一个最大值，设置变量1 res = Integer.MAX_VALUE 和变量2 count = 0 （用来计算subarry的和）
2. for 循环 设置 左右窗口 i j 来循环整个array
3. count 加上右窗口走过的数
4. 当count >= target 的时候 呼叫while 来找寻最小区间
5. 找寻最小区间，顺便动用 左框 压缩subarray
6. 注意有可能不存在因此还要在return的时候判断一下 不存在就return 0
代码如下

1. 
   
2. class Solution {
   
3.     public int minSubArrayLen(int target, int[] nums) {
   
4.         int res = Integer.MAX_VALUE;
   
5.         int count = 0;
   
6.         for(int i = 0, j = 0; i < nums.length; i++){
   
7.             count += nums[i];
   
8.             while(count >= target){
   
9.                 res = Math.min(i - j + 1, res);
   
10.                 count -= nums[j++];
    
11.             }
    
12.         }
    
13.         return res == Integer.MAX_VALUE ? 0 : res ;
    
14.     }
    
15. }
    

复制代码

第二题，subarray product less than k
一般碰到这种题，就基本上确定要使用 滑动窗口 + prefix sum的战术了
基本上套路和第一题一样。
i j 齐头并进 while循环处理特殊情况
这次的图书情况是 subarray的product 必须小于k 因此 while循环就处理 > k的情况。范围控制就在while之外搜索
特别注意的一点是 注意 右窗口别超过左窗口

1. 
   
2. class Solution {
   
3.     public int numSubarrayProductLessThanK(int[] nums, int k) {
   
4.         int res  = 0;
   
5.         int count = 1;
   
6.         for(int i = 0, j = 0; i < nums.length; i++){
   
7.             count *= nums[i];
   
8.            // 注意左右窗口
   
9.             while(j <= i && count >= k){
   
10.                 count /= nums[j++];
    
11.             }
    
12.             res += i - j + 1;
    
13.         }
    
14.         return res;
    
15.     }
    
16. }
    

复制代码

1004 哎呦 这题更明显了，就差名字起名叫 我是滑动窗口了
这题主要检测 k， 设置一个临时变量，右窗口是0 就把临时变量count ++， 当超过了 k 就开始缩小subarray
然后找到max subarray

1. 
   
2. class Solution {
   
3.     public int longestOnes(int[] nums, int k) {
   
4.         int res = 0, count = 0;
   
5.         for(int i = 0, j = 0; i < nums.length; i++){
   
6.             if(nums[i] == 0) count++;
   
7.             while(count > k){
   
8.                 if(nums[j] == 0) count --;
   
9.                 j++;
   
10.             }
    
11.             res = Math.max(i - j + 1, res);
    
12.         }
    
13.         return res;
    
14.     }
    
15. }
    

复制代码

2024 是我认为这四道题里 最难的一题。难在这题是为了做题而出的，没有什么人类的行为逻辑可言
歌词大意就是超过了k个 就把t换成f 或者f换成t 看最长的subarray是多少。一开始读题的时候，我一直在想为什么。后来就觉得跟抖音一样，有些视频他就是没有逻辑。就是很烂。下滑就好了

题还是要做的

1. 
   
2. class Solution {
   
3.     public int maxConsecutiveAnswers(String answerKey, int k) {
   
4.         int res = 0, countF = 0, countT = 0;
   
5.         for(int i = 0, j = 0; i < answerKey.length(); i++){
   
6.             char ch = answerKey.charAt(i);
   
7.             if(ch == 'F') countF ++;
   
8.             else countT ++;
   
9.             while(countF > k && countT > k){
   
10.                 char temp = answerKey.charAt(j);
    
11.                 if(temp == 'F') countF --;
    
12.                 else countT --;
    
13.                 j++;
    
14.             }
    
15.             res = Math.max(i - j + 1, res);
    
16.         }
    
17.         return res;
    
18.     }
    
19. }
    

复制代码

谢谢分享