leetcode---904. 水果成篮 -- 【滑动窗口/c++】

原题：904. 水果成篮 - 力扣（LeetCode）

题目解析：

本题中的fruit数组中的元素表示的是数的种类。如示例1，fruit【1,2,1】就表示下标0处有1号类型的树，下标1处有2号类型的树，下标2处有1号类型的树。

而最多只能摘两种类型的果子，在示例1中就是，从下标0开始 有 1,2,1可以摘遍所有树；或者从下标1开始 有 2，1只能摘两颗树。所以在示例1中，怎么摘都不会超过两种种类的果子。

现在要求返回收集果子的最大数目，其实就是求最长的连续子串是多少。

所以整个题目就是在说：求最长的子数组长度，子数组中的元素种类不超过两个。（水果种类不超过两个）

算法原理：

为判断摘的果子种类是否超过两种，用哈希表来记录摘的果子的种类。

而哈希表的长度就表示含有的种类数。

用暴力解法的话就是从左到右遍历，依旧是双指针，然后枚举所有可能情况。

用滑动窗口进行优化，因为当种类数超过2时，右指针其实不用回到左指针位置重新遍历，此时左右指针内的所有元素个数和就表示从左指针开始能达到的最大值（最多水果个数），这时只要左指针移动，直到哈希表中的长度等于2为止。

滑动窗口四步走：

进窗口 --- 哈希表对应种类++

判断 --- 哈希表长度是否大于2

出窗口 --- 左指针向前移动，直到哈希表长度等于2

更新状态 --- 将最大的子数组长度赋值给ret返回值

代码编写：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int>hash; //创建哈希表
        
        int ret = 0;
        for(int left = 0,right = 0;right<fruits.size();right++)
        {
            //进窗口
            hash[fruits[right]]++;

            //判断
            while(hash.size() >2)
            {
                //出窗口
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) //这个种类的水果都没了
                {
                    hash.erase(fruits[left]);
                }
                left++;
            } 
            //更新状态
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};

优化时间复杂度

省去对哈希表增删的操作时间

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0}; //创建哈希表
        
        int ret = 0;
        for(int left = 0,right = 0,kinds = 0;right<fruits.size();right++)
        {
            //进窗口
            if(hash[fruits[right]] == 0)
            {
                kinds++;
            }
            hash[fruits[right]]++;
            
            //判断
            while(kinds >2)
            {
                //出窗口
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) //这个种类的水果都没了
                {
                    kinds--;
                }
                left++;
            } 
            //更新状态
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};