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
