本篇博客是我对“水果成篮”这道题由暴力解法到滑动窗口思路的具体思路，有需要借鉴即可。
1.题目
题目链接：LINK
这道题，题干很长，大概意思是给你一个数组，然后你可以从随便一个数字开始依次遍历，直到遍历结束或者找到超过不同的两个数字，问你最大长度是几。
一般没有经验的人，肯定首先想到的是暴力求解，我也是一样哈，没啥经验。
2.暴力求解
那如何进行暴力求解呢？
暴力求解思路：哈希表 + 依次遍历
思路详解：具体来说，定义两个指针，一个left，一个right，再搞一个哈希表，right指向的数字就丢到哈希表里，计数，然后超过两个或者遍历结束的时候，我们更新一下结果然后left++，right = left，重新计数。然后这堆记的数字取个最大的就行了。
总而言之，代码如下：
class Solution { public: //暴力解法： int totalFruit(vector<int>& fruits) { int n = fruits.size(); int count = 0; int ret = 0; int sum = 0; for(int left = 0;left < n;left++) { count = 0; sum = 0; int hash[100001] = {0}; for(int right = left;right < n;right++) { //进哈希表 if(hash[fruits[right]] == 0)//一个新种类的水果 { hash[fruits[right]]++; count++; sum++; } else//这里标识之前有过的一个水果 { hash[fruits[right]]++; sum++; } if(count > 2) { ret = max(ret, sum - 1);break; } if(count <= 2 && right == n - 1) {ret = max(ret, sum);break;} } } return ret; } };
然后不出意外哈，力扣绝对过不了，不然这题不会上中等难度了。
然后力扣提示说超出时间限制，比如下图：
所以说，这道题肯定是可以优化的，那具体怎么优化呢？我们一步一步来。
3.暴力优化
3.1每次right不用回退
这是什么意思呢？如下图所示：
在left固定的情况下，之后right这个地方数字种类超过2了，那么意思是红色这块区域数字种类个数是2，这时候按照暴力求解的方式，left++，right = left。
但是，我想说绿色的这块区域的数字种类会有可能超过2吗？显然这是不可能的，所以说right压根没有回去的必要。
3.2有些left长度一定不如前一个，不用走，left不回退
再比如说哈，如下图所示：
left = 2的情况下压根没必要去走好吧~~
行了，这时候我就发现这个题目经过优化之后满足“滑动窗口”的使用条件，两指针同向且不回退。
4.滑动窗口算法
然后可以直接优化成滑动窗口算法
class Solution { public: //滑动窗口： int totalFruit(vector<int>& fruits) { int n = fruits.size(), ret = 0,sum = 0,kands = 0; int hash[100001] = {0};//哈希数组 for(int right = 0, left = 0;right < n;right++) { //进窗口 if(hash[fruits[right]] == 0)kands++;//如果这个是一个新来的数，那么就种类++ hash[fruits[right]]++; sum++; //出窗口 while(kands > 2) { hash[fruits[left]]--; sum--; if(hash[fruits[left]] == 0)kands--; left++; } ret = max(ret, sum); } return ret; } };
5.总结
总结一下这个题，我感觉正常做的话能做出来，也没啥坑，我感觉是属于一个很常规的滑动窗口的题目。
EOF
