904. 水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
题目链接：https://leetcode.cn/problems/fruit-into-baskets
示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
思路：
首先这道题理解起来就较有难度，数组中的数表示的是水果的种类，即每一个数字都代表一种水果。我一开始傻傻的理解为是树上水果种类的个数，看了示例才明白过来。
在理解问题的基础上，可以发现，这也是一道寻找最长子序列的问题，这次的限制条件就是，子序列中最多含有两种类型的水果，即两种数。
滑动窗口+哈希表：
因为这道题目又涉及到了求最长或最短子序列的问题，所以自然而然我们也可以使用滑动窗口的方法进行求解。而本题的另一个难点就在于，如何让窗口进行变动，缩小窗口。题目中的限制条件就是，所拿的水果种类不能够超过两种，所以我们有必要记录目前所含有的水果种类。针对这个问题，哈希表是非常适合的。
class Solution {
public:
//滑动窗口
int totalFruit(vector<int>& fruits) {
int ans[100000] = { 0 };//简易哈希表，并初始化，用于记录不同种类水果的个数
int result = 0; //让result取0（因为要求的是最大值）
int sum = 0; // 数组中已有水果的种类
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < fruits.size(); j++) { //j指向滑动窗口的末尾位置，用来遍历
if (ans[fruits[j]] == 0) //若该种类水果的个数为0
{
sum++;//添加新水果，水果种类增加
}
ans[fruits[j]]++;//该种水果数量加一
while (sum > 2) //当水果的种类大于2时，要进行删除一类水果的操作
{
ans[fruits[i]]--; //删除当前种类的水果
if (ans[fruits[i]] == 0)//收缩至有一种水果个数为0
{
sum--;//水果种类减少
}
i++;//删除水果的过程即缩小窗口大小的过程
}
subLength = j - i + 1;
result = result > subLength ? result : subLength;
}
return result;
}
};
哈希表的实现方式有三种：数组、set、map。这里由于题目中提示已告诉我们，水果的种类不超过10000种，所以我们可以建立一个大小为10000的数组，并初始化所有值为零，从而建立一个哈希表。
而剩下的部分，则为常规的滑动窗口问题，用两个指针进行遍历，不断调整窗口的大小，最终寻找到符合条件的值。
往期回顾：
LeetCode977.有序数组的平方
LeetCode844.比较含退格的字符串
LeetCode283.移动零
LeetCode27.移除元素
LeetCode26.删除有序数组中的重复项
LeetCode209.长度最小的子数组
