LeetCode 904.水果成篮

LeetCode 904.水果成篮

思路🧐：

  求水果的最大数目，也就是求最大长度，我们是单调的向前求解，则能够想到使用滑动窗口进行解答，可以用hash表统计每个种类的个数，kinds变量统计当前种类，left和right表示左边框和右边框，且都从起点开始。

  右边框先走，当种类个数为0时，表示这是个新种类，kinds++，当kinds大于2，则不满足题意，需要删减旧的种类，再移动左边框，当种类个数为0时，旧种类删减完成，继续移动右边框，重复该过程并每次循环都算一下长度，直到right走到尾结束。

代码🔎：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = { 0 }; //针对题目数据范围优化
        int len = 0;
        for(int left = 0, right = 0, kinds = 0; right < fruits.size(); right++)
        {
            if(hash[fruits[right]] == 0) //如果哈希表对应的水果下标为0，就表示有一个新的种类
                kinds++;
            hash[fruits[right]]++; //对应下标修改个数
            while(kinds > 2) //当种类大于2，表示不能再装了，需要消除旧的种类
            {
                hash[fruits[left]]--; //对应hash表减去该种类个数
                if(hash[fruits[left]] == 0) //当减到0，表示旧的种类没有了
                    kinds--; //种类减少
                left++; //移动左边框
            }
            len = max(len, right - left + 1); //长度计算
        }
        return len;
    }
};

return len;

}

};

![image-20241124191735745](https://img-blog.csdnimg.cn/img_convert/6b419397b927e6f34c470b60ba8ea3fd.png)