力扣算法之滑动窗口题目--水果成篮

题目解析

首先我们先看一下题目如下图所示

题目意思也比较容易理解其实就是你有一个篮子这个篮子只能装两个不同种类的水果，问你最多能装多少个水果，这里还贴心的弄了一个样列，121 可以看出来1和2是两个不同种类的水果所以这个篮子可以装三个水果另外就是这个题目还要求我们不能跳过某棵树摘取水果（这个特点很重要）。好的那么现在跟上节奏我们看一看这个题目跟我们平常见到的滑动窗口问题有什么不同之处。

不同之处

好的那么我们知道了这个题的题目意思之后呢我们想一下之前我们做滑动窗口的时候比较简单的窗口问题会贴心的告诉你窗口的大小对吧，但是这个题目只说了最大时两种水果没说做大可以装多少个水果，因此其实这个时滑动窗口的一种运用。

解决办法

那么我们知道了这个题目的意思以及特点后我们来看一下这个题目的解决办法，首先就是我们之前的题目都是用窗口内的元素多少与窗口大小进行比较，从而判断是否需要出窗口，而这个题目呢使用的是说如果种类数超过2才出窗口
那么首先我们要先知道我们这个篮子里的种类数有多少，那这样的话就需要我们有一个变量去保存这个窗口内的种类数，其次我们则么知道这个数字在不在窗口内呢，很简单用一个hash表去记录一下就可以了啊因为我们要注意这个数字是大于0的所以我们可以直接用一个一维数组的下标去判断即可，那么在这个窗口内的元素就让hash[num[i]]++(假设num[i]这个数字在这个窗口内)这样字就可以知道这个数字在窗口内，如果需要出窗口的话同样也只需要我们hash[num[i]]–;即可。
好的那么接下来就倒了我们的老朋友出场也就是我们在滑动窗口问题中经常用到的两个指针left和right

解决图示

1首先left和right指向同一个位置，然后right一直向右移动。

2当right移动到2的时候我们发现此时2如果进入到窗口中那么会导致种类数大于2那么现在需要出窗口。出窗口怎么出呢？

3出窗口也很简单就是让left一直向左移动一直移动到窗口内的水果种类数满足小于等于2为止。

代码

好的那么解释了这么长时间我们就可以实现代码并作出代码的解析了

class Solution {
public:
    int totalFruit(vector<int>& f) {
        vector<int> hash(100010, 0);
        int left = 0;
        int kinds = 0;
        int ans = 0;
        for (int right = 0; right < f.size(); right++) {
            if (hash[f[right]] == 0)kinds++;
            hash[f[right]]++;
            while (kinds > 2) {
                hash[f[left]]--;
                if (hash[f[left]] == 0)
                    kinds--;
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

首先在这个代码中，我们的kinds就是计算窗口内的种类数的hash数组就是来保存一下当前数字在不在窗孔内。那么代码主体部分也就是for循环那里，我们可以看到，首先就是先判断，hash[f[left]]是否等于0如果等于0的话也就是说不在窗口内那么就可以kinds++代表窗口内的种类数++然后让他入窗口（为什么必须入呢因为题目要求了大家可以仔细看看）然后再使用while循环判断kind是否大与2如果大于2 那就让其减小到2（也就是出窗口）出窗口就是hash[f[left]]–并且一定要先判断当前left指向的数字是否缩小为0然后决定种类数是否需要–之后再让left++。再次期间有些同学可能会有疑问比如说某个数字是和窗口内不需要出窗口的数字是一样的也就是出现同样是2但是却不在窗口内的情况这样结果也是正确的因为题目说明了这样的情况比如下图所示

这种情况是可能发生的但是题目要求我们必须连续的才可以因此不影响我们做题。