本題鏈接??水果成籃
第一步：了解題意
我就按照實(shí)例1來(lái)進(jìn)行對(duì)這題的理解。
1代表種類類型，這個(gè)數(shù)組里面有2個(gè)種類類型 ps:種類1和種類2 ，只不過(guò)種類1是有2個(gè)水果，種類2有一個(gè)水果，共計(jì)3個(gè)水果。
本題需要解答：收集水果的最大數(shù)目.
但是前提條件：
- 我們只有2個(gè)籃子，每個(gè)籃子里只能裝1種類型，但是籃子里的數(shù)量是不限制的。
- 每采摘一次，將會(huì)可以向右移動(dòng)到下一棵樹(shù)，并繼續(xù)采摘，不能跳過(guò)一棵樹(shù)
- 2個(gè)籃子表示著我們只能容納2個(gè)類型的，出現(xiàn)第3類型的蘋(píng)果，我們就直接結(jié)束采摘
就按實(shí)例3來(lái)表示：fruits[1，2，3，2，2]?
1，2，遇到3的時(shí)候，這就是我們遇到的第三種類型水果了，那么我們就需要停止，這時(shí)候就可以記錄一次蘋(píng)果的數(shù)量2，其實(shí)后面就不用看了。
然后就從2開(kāi)始，因?yàn)?，3是2種類型就可以繼續(xù)采摘，大于2才是不行的，所以2，3，2，2，一直是可以的，因?yàn)槎际欠N類2，相當(dāng)于同一種類型，所以蘋(píng)果數(shù)量是4，這時(shí)候最大的采摘數(shù)量是4.?
第二步：算法思路
以后我們遇到一些題目記錄一些重復(fù)值個(gè)數(shù)，如果超過(guò)幾個(gè)數(shù)或者不能重復(fù)，就需要將這個(gè)值存入到哈希表中（其實(shí)就是值得映射到數(shù)組中去）
大部分題目都是從 暴力枚舉 然后一步一步的優(yōu)化得到的，所以
第一種解法：暴力枚舉+哈希
首先定義2個(gè)指針，都是在0位置出發(fā)。
暴力枚舉中的第二步，每一次都得清空hash中的值，我們就會(huì)覺(jué)得很繁瑣，那么如何優(yōu)化呢？
第二種解法：滑動(dòng)窗口+哈希
滑動(dòng)窗口的模板：
1.left=0,right=0;
2.進(jìn)窗口
3.判斷
4.出窗口
更新結(jié)果（這是是在上面的4個(gè)步驟中根據(jù)題目的不同來(lái)穿插的）
2.進(jìn)窗口
實(shí)際上，就是讓right的值存入到hash表中（hash表其實(shí)就是一個(gè)一維數(shù)組）
3.判斷
我們上面再了解題意的時(shí)候已經(jīng)寫(xiě)上了（種類超過(guò)2種的就得停止采摘）
所以判斷的條件就是是否超過(guò)2種種類。
4.出窗口
出窗口建立在判斷的時(shí)候的 ，判斷了超過(guò)2種類型，我們就得出窗口，left對(duì)應(yīng)的值就得--，如果減到0了我們就得給種類-1，知道減到種類=2，left++,我們就可以繼續(xù)進(jìn)行滑動(dòng)窗口的步驟。
5.更新結(jié)果
結(jié)果是只要判斷結(jié)果kinds<2就可以更新結(jié)果。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-795905.html
第三步：代碼實(shí)現(xiàn)
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001]={0};//統(tǒng)計(jì)窗口中出現(xiàn)了多少種水果
int ret=0;
for(int left=0,right=0,kinds=0;right<fruits.size();right++)
{
if(hash[fruits[right]]==0) kinds++;
hash[fruits[right]]++;//進(jìn)窗口
while(kinds>2)//判斷
{
//出窗口
hash[fruits[left]]--;//left對(duì)應(yīng)的值一直--
if(hash[fruits[left]]==0) kinds--;//直到-到0就給種類--
left++;
}
ret=max(ret,right-left+1);
}
return ret;
}
};我永遠(yuǎn)走在提升自己的路上~?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-795905.html
到了這里，關(guān)于力扣精選算法100題——水果成籃(滑動(dòng)窗口專題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
