904. 水果成籃
你正在探訪一家農(nóng)場，農(nóng)場從左到右種植了一排果樹。這些樹用一個整數(shù)數(shù)組 fruits 表示，其中 fruits[i] 是第 i 棵樹上的水果 種類 。
你想要盡可能多地收集水果。然而，農(nóng)場的主人設定了一些嚴格的規(guī)矩，你必須按照要求采摘水果：
- 你只有 兩個 籃子，并且每個籃子只能裝 單一類型 的水果。每個籃子能夠裝的水果總量沒有限制。
- 你可以選擇任意一棵樹開始采摘，你必須從 每棵 樹（包括開始采摘的樹）上 恰好摘一個水果 。采摘的水果應當符合籃子中的水果類型。每采摘一次，你將會向右移動到下一棵樹，并繼續(xù)采摘。
- 一旦你走到某棵樹前，但水果不符合籃子的水果類型，那么就必須停止采摘。
給你一個整數(shù)數(shù)組 fruits ，返回你可以收集的水果的 最大 數(shù)目。
題目鏈接：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
思路：
首先這道題理解起來就較有難度，數(shù)組中的數(shù)表示的是水果的種類，即每一個數(shù)字都代表一種水果。我一開始傻傻的理解為是樹上水果種類的個數(shù)，看了示例才明白過來。
在理解問題的基礎上，可以發(fā)現(xiàn)，這也是一道尋找最長子序列的問題，這次的限制條件就是，子序列中最多含有兩種類型的水果，即兩種數(shù)。
滑動窗口+哈希表：
因為這道題目又涉及到了求最長或最短子序列的問題，所以自然而然我們也可以使用滑動窗口的方法進行求解。而本題的另一個難點就在于，如何讓窗口進行變動，縮小窗口。題目中的限制條件就是，所拿的水果種類不能夠超過兩種，所以我們有必要記錄目前所含有的水果種類。針對這個問題，哈希表是非常適合的。
class Solution {
public:
//滑動窗口
int totalFruit(vector<int>& fruits) {
int ans[100000] = { 0 };//簡易哈希表，并初始化，用于記錄不同種類水果的個數(shù)
int result = 0; //讓result取0（因為要求的是最大值）
int sum = 0; // 數(shù)組中已有水果的種類
int i = 0; // 滑動窗口起始位置
int subLength = 0; // 滑動窗口的長度
for (int j = 0; j < fruits.size(); j++) { //j指向滑動窗口的末尾位置，用來遍歷
if (ans[fruits[j]] == 0) //若該種類水果的個數(shù)為0
{
sum++;//添加新水果，水果種類增加
}
ans[fruits[j]]++;//該種水果數(shù)量加一
while (sum > 2) //當水果的種類大于2時，要進行刪除一類水果的操作
{
ans[fruits[i]]--; //刪除當前種類的水果
if (ans[fruits[i]] == 0)//收縮至有一種水果個數(shù)為0
{
sum--;//水果種類減少
}
i++;//刪除水果的過程即縮小窗口大小的過程
}
subLength = j - i + 1;
result = result > subLength ? result : subLength;
}
return result;
}
};
哈希表的實現(xiàn)方式有三種：數(shù)組、set、map。這里由于題目中提示已告訴我們，水果的種類不超過10000種，所以我們可以建立一個大小為10000的數(shù)組，并初始化所有值為零，從而建立一個哈希表。
而剩下的部分，則為常規(guī)的滑動窗口問題，用兩個指針進行遍歷，不斷調(diào)整窗口的大小，最終尋找到符合條件的值。
往期回顧：
LeetCode977.有序數(shù)組的平方
LeetCode844.比較含退格的字符串
LeetCode283.移動零
LeetCode27.移除元素
LeetCode26.刪除有序數(shù)組中的重復項
LeetCode209.長度最小的子數(shù)組
