leetcode904.水果成篮题解

• 滑动窗口
• • 什么是滑动窗口
• 长度最小的子数组
• 水果成篮
• 最后

大家好，我是青菜不青。
今天想分享的是做题时候遇到的一类题型，希望对在看的小伙伴们有所帮助！
希望大家一起不断成长。

滑动窗口

在解题之前，我们来认识一下为我们解决这个题目的一个很关键的技巧----滑动窗口这是我们后续做题的核心。在了解了滑动窗口的概念之后，会先分享一道简单一点的这类题目，之后才是水果成篮~

什么是滑动窗口

滑动窗口是我们在数组中某些题目中使用到的一些技巧。

这类题目的共同特点就是：

• 使用两个变量，或者称为指针，同时维护，用来当作窗口的边界
• 右指针右移，然后左指针跟着右移，循环这个动作，直到右指针遍历完整个数组

如下图所示：在我们维护两指针的过程中，像一个窗口在滑动，于是就被起名叫滑动窗口类型的题型。其实也就是双指针。

注意滑动窗口的窗口，此处虽然画的是固定长度，但是对于这类题目来说，可以分为固定长度的滑动窗口问题和不固定长度的滑动窗口

我们为什么需要使用滑动窗口呢？

主要就是效率，我们当然也可以暴力求解一些问题，但是效率是低下的。引用双指针就能将时间复杂度从O(N^2)变成O(N)，这样提高效率是成倍提高的。

话不多说，我们从题目中体会吧！

长度最小的子数组

leetcode209

我们先用暴力求解来体会一些此题：

• 从第一个数开始求以它为开头的>=target连续子数组
• 重复上述过程到第二个数/第三个数/第四个数/…
• 找出最小长度子数组

我们以第一个示例为例子

第一次是2开头的：[2,3,1,2] 和为8 >=7 长度为4

第二次是3开头的：[3,1,2,4] 和为10 >= 7 长度为4

第三次是1开头的：[1,2,4] 和为 7 >= 7 长度为3

第四次是2开头的：[2,4,3] 和为9 >= 7 长度为3

第五次是4开头的：[4,3] 和为 7 >= 7 长度为2

第六次是3开头：不满足 >=7

我们定义一个minCount，每次记录一个子数组的长度就与之比较，取小赋值给minCount。

class Solution {     public int minSubArrayLen(int target, int[] nums) { int minCount = 10000; int count = 0; int sum = 0; for(int i = 0; i < nums.length; i++) {     sum = 0;     for(int j = i; j < nums.length; j++) {  sum+=nums[j];    if(sum >= target) {      count = j - i + 1;      break;  }    }     if(minCount > count){  minCount = count;     } } return minCount;    }}

接下来来看看滑动窗口的写法：

与暴力的思路差不多

只不过在找到某一个子数组之后，就将左指针++，找下一个子窗口。同时sum减去未加加前的左指针值。

注意此处就是导致时间复杂度的关键。暴力中我们每一次循环都要重新计算sum，此处我们并没有，sum加过的元素，一直在sum中，直到左指针指向这些元素，才被减去，也就是我们虽然在两重循环中，但是对元素操作也只是两次而已，时间复杂度是O(2N)

class Solution {    public int minSubArrayLen(int target, int[] nums) { int left = 0; int right = 0; int sum = 0; int minLen = 10000; int len = 0; while(right < nums.length){     sum+=nums[right];     right++;     while(sum >=target){  minLen = Math.min(minLen,right - left);  sum = sum - nums[left];  left++;     } } if(minLen == 10000){     return 0; } return minLen;    }}

水果成篮

😭😭😭万恶的水果成篮

这个题目，重在理解题目😭

leetcode904

开始看到题目的时候，《其中first[i]是第i棵树上水果的种类》，这句话我以为是一种=颗树上可以长不同的水果。😭比如first[1]=2，我就以为是第一棵树上有两种水果！！！漏！大漏特漏！

first[1] = 2的真正意义是长的是第二棵树的水果。

也就是说我们要维护的窗口内的数字种类不能超过2，求出最长的窗口大小即可。

1,2,2 ---->这叫两种种类水果

1,2,2,3,3,3 ---->这叫三种种类水果

class Solution {    public int totalFruit(int[] fruits) { if(fruits.length <= 2){     return fruits.length; } int left = 0; int right = 0; int MaxCount = 0; int ltree = fruits[left],rtree = fruits[right]; while(right < fruits.length){     //这是保证了至多两种水果的if判断     if(fruits[right] == rtree || fruits[right] == ltree){  MaxCount = Math.max(MaxCount, right - left + 1);  right++;     }else{  //在这一步left=right-1,这个值肯定是和fruits[right]不一样的,就是不一样才会导致进入else  left = right - 1;  ltree = fruits[left];  while(left >= 1 &&fruits[left-1] == ltree){      left--;//找到等于fruits[left]的起始位置  }  rtree = fruits[right];  MaxCount = Math.max(MaxCount, right - left + 1);     } } return MaxCount;    }}

最后

在解这类题目的时候把握住如何根据题目的意图维护两个指针，就是关键

ps：我是在这几天才知道原来win+。可以打出表情的😏
以前一直以为大佬们文章里的表情是手机编写的🤡
文字如果有错误，请各位及时指正哟~🤪