【算法专题突破】滑动窗口 - 水果成篮（13）

目录

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

---

1. 题目解析

题目链接：904. 水果成篮 - 力扣（Leetcode）

题目有很长一段话，但是我们读一遍题目可以提炼转化出题目的要求 ：

其实就是找出一个最长的子数组，且数组内数字的种类不超过两个。

2. 算法原理

这道题题目可以使用滑动窗口来解决，

为什么呢？

我们可以来简单分析一下，

我们通过哈希表维护一个窗口，

让right++进窗口，如果出现了三个种类的水果，就让left++，

left++会有两种情况，

1. 还是有三种水果，那就让left继续++

2. 剩两种水果了，那就记录结果，这个时候重点来了，

right需不需要回到left的位置重新++呢？不需要，这就是滑动窗口的核心，

我们直接让right继续++进窗口即可。

3. 代码编写

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> win;
        int kinds = 0, left = 0, right = 0, len = 0;
        while(right < fruits.size()) {
            win[fruits[right++]]++;
            while(left < fruits.size() && win.size() > 2) {
                win[fruits[left++]]--;
                if(win[fruits[left - 1]] == 0) {
                    win.erase(fruits[left - 1]);
                    break;
                }
            }
            len = max(len, right - left);
        }
        return len;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~