1. 题⽬链接：904.⽔果成篮
2. 题⽬描述：
3. 解法（滑动窗⼝）：
算法思路：
研究的对象是⼀段连续的区间，可以使⽤「滑动窗⼝」思想来解决问题。 让滑动窗⼝满⾜：窗⼝内⽔果的种类只有两种。
做法：
右端⽔果进⼊窗⼝的时候，⽤哈希表统计这个⽔果的频次。这个⽔果进来后，判断哈希表的 ⼤⼩：
▪ 如果⼤⼩超过2：说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗 ⼝，直到哈希表的⼤⼩⼩于等于2，然后更新结果；
▪ 如果没有超过2，说明当前窗⼝内⽔果的种类不超过两种，直接更新结果ret。
算法流程：
a. 初始化哈希表hash来统计窗⼝内⽔果的种类和数量；
b. 初始化变量：左右指针left=0，right=0，记录结果的变量ret=0；
c. 当right⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
i. 将当前⽔果放⼊哈希表中；
ii. 判断当前⽔果进来后，哈希表的⼤⼩：
• 如果超过2：
◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
◦ 如果这个元素的频次减⼀之后变成了0，就把该元素从哈希表中删除；
◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过2；
iii. 更新结果ret； iv. right++，让下⼀个元素进⼊窗⼝；
d. 循环结束后，ret存的就是最终结果。
C++算法代码（使⽤容器）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果
int ret = 0;
for (int left = 0, right = 0; right < f.size(); right++)
{
hash[f[right]]++; // 进窗⼝
while (hash.size() > 2) // 判断
{
// 出窗⼝
hash[f[left]]--;
if (hash[f[left]] == 0)
hash.erase(f[left]);
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
C++算法代码（⽤数组模拟哈希表）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
int ret = 0;
for (int left = 0, right = 0, kinds = 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++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
C++算法代码<使用map>：
map<char, int>mp;
class Solution
{
public:
int totalFruit(vector<int>& fruits)
{
int count = 0; //记录水果种类数
int maxnum = 0; //水果最大数目
int num = 0; //记录每个子序列中的水果数目
map<int, int>mp;
for (int i = 0; i < fruits.size(); i++)
{
mp[fruits[i]] = 0;
}
//滑动窗口
int left = 0, right = 0;
for (; right < fruits.size(); right++)
{
//记录水果种类
if (mp[fruits[right]] == 0)
{
count++;
}
mp[fruits[right]]++;
//进窗口
if (count <= 2)
{
num=right-left+1;
}
//退窗口
while(count > 2)
{
maxnum = max(maxnum, num);
mp[fruits[left]]--;
//当子序列中水果种类回到2时停止退窗口操作
if (mp[fruits[left]] == 0)
{
left++;
count -= 1;
break;
}
left++;
}
maxnum = max(maxnum, num);
}
return maxnum;
}
};Java算法代码（使⽤容器）：
class Solution
{
public int totalFruit(int[] f)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // 统计窗
⼝内⽔果的种类
int ret = 0;
for (int left = 0, right = 0; right < f.length; right++)
{
int in = f[right];
hash.put(in, hash.getOrDefault(in, 0) + 1); // 进窗⼝
while (hash.size() > 2)
{
int out = f[left];
hash.put(out, hash.get(out) - 1); // 出窗⼝
if (hash.get(out) == 0)
hash.remove(out);
left++;
}
// 更新结果
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}
Java算法代码（⽤数组模拟哈希表）：
class Solution
{
public int totalFruit(int[] f)
{
int n = f.length;
int[] hash = new int[n + 1]; // 统计窗⼝内⽔果的种类
int ret = 0;
for (int left = 0, right = 0, kinds = 0; right < n; right++)
{
int in = f[right];
if (hash[in] == 0) kinds++; // 维护⽔果种类
hash[in]++; // 进窗⼝
while (kinds > 2) // 判断
{
int out = f[left];
hash[out]--; // 出窗⼝
if (hash[out] == 0) kinds--;
left++;
}
// 更新结果
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}