中等
思路： 1、直接暴力解904. 水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
类似双指针的滑动窗口，定义左指针（慢，i）和右指针（快，j），定义一个sum 是记录这次能装多少个水果，定义type1,type2记录两种水果的种类。慢指针指向装的第一个水果（顺便定义了type1 = fruits[i]），定义 k 代表第二种水果第一次出现的位置（顺便定义了type2 = fruits[k]），快指针从0开始循环，往右移动的过程中，每次移动需要判断 fruits[j] 是否等于type1或type2中的一个，如果等于，sum++ ；如果不等于，就需要重置，即挪动 i 指针，第一种方法是直接 i++，sum--, 太费时间；第二种方法是直接把 i 移到 第二种水果第一次出现的位置即 k ,此时 sum也需要更新为 sum - (k - i) 。应该就差不多了。
class Solution {
public:
int totalFruit(vector& fruits) {
//符合只有两个不同数的，最长子序列，滑动窗口 15：22 （5月底没想完）
//7.2 继续想20:00开始,想到21.30也没AC 纯傻逼;
//7.4下午3.10又开始debug，暴力解应该没问题了，就是超出时间限制，o(n^2)
//7.4 想更新i-----16.44通过了，注意，滑动窗口i跳了的话，Sum也得跳
int i = 0;
int sum = 1;
int type1 = -1;
int type2 = -1;
int result = 0;
//边界情况，输入[0]
if(fruits.size() == 1) return 1;
//快指针在外循环
for (int j = 1; j < fruits.size(); j++){
//定义type1
type1 = fruits[i];
// if((fruits[j] != type1) && (type2 == -1)) type2 = fruits[j]; //初值赋的不对，这样会跳过中间某些数如 [3,3,3,1,2,1,1,2,3,3,4]
//定义type2 出现在 k处
int k = i; //k的位置也很重要，必须在这个外面
if((fruits[j] != type1) && (type2 == -1)){
for(;k<=j;k++){
if(fruits[k]!=fruits[i]){
type2 = fruits[k];
break;
}
}
}
if((fruits[j] == type1) || (fruits[j] == type2)){
sum++;
if(sum > result) {
result = sum; // result = j - i + 1; //都可以
//cout<<"result (in j = "<
白板输出：
class Solution904 {
public:
int totalFruit(vector& fruits) {
//符合只有两个不同数的，最长子序列，滑动窗口 15：22 （5月底没想完）
//7.2 继续想20:00开始
int i = 0;
int sum = 1;
int type1 = -1;
int type2 = -1;
int result = 0;
int k = -1;
//边界情况，输入[0]
if(fruits.size() == 1) return 1;
//快指针在外循环
for (int j = 1; j < fruits.size(); j++){
cout<<"j: "< result) {
result = sum; //way1
//result = j - i + 1;
cout<<"type1,2: " << type1 << " " < fruits1 ;
for(int i = 0;i<3;i++){
fruits1.push_back(arr1[i]);
cout< fruits2 ;
for(int i = 0;i<4;i++){
fruits2.push_back(arr2[i]);
cout << fruits2[i]<<" ";
}
cout << endl;
cout << "示例输出:" < fruits41 ;
for(int i = 0;i<11;i++){
fruits41.push_back(arr41[i]);
cout << fruits41[i]<<" ";
}
cout << endl;
cout << "示例输出:" < fruits68 ;
fruits68.push_back(arr68[0]);
cout << endl;
cout << "示例输出:" < fruits3 ;
for(int i = 0;i<2;i++){
fruits3.push_back(arr3[i]);
cout << fruits3[i]<<" ";
}
cout << endl;
cout << "示例输出:" < fruits69 ;
for(int i = 0;i<7;i++){
fruits69.push_back(arr69[i]);
cout << fruits69[i]<<" ";
}
cout << endl;
cout << "示例输出:" < fruits80 ;
for(int i = 0;i<8;i++){
fruits80.push_back(arr80[i]);
cout << fruits80[i]<<" ";
}
cout << endl;
cout << "示例输出:" <
2、其他解法
来自leetcode评论区
（1）上面暴力解的改进版，在循环 j 时就顺便把第二种水果第一次出现的位置记录下来
力扣 C++ 双指针，可以用一个单独指针指向left下一次跳转的位置，也可以先left=right-1,再进行回退
class Solution {
public:
int totalFruit(vector& fruits) {
int left = 0, right = 0; // 双指针法，自己想到的！
int firstSort = -1, secondSort = -1;
int maxCount = 0; // 可以收集的最大数目
int thirdBefore = 0; // thirdBefore指向第三种果树的前一种果树的第一棵
firstSort = fruits[left];
for (right = 0; right < fruits.size(); right++) {
if (fruits[right] != firstSort && secondSort == -1) {
secondSort = fruits[right];
}
if (fruits[right] == firstSort || fruits[right] == secondSort) {
maxCount = right - left + 1 > maxCount ? right - left + 1 : maxCount;
} else {
left = thirdBefore; // 移动慢指针
firstSort = fruits[left];
secondSort = fruits[right];
}
if (right > 0 && fruits[right] != fruits[right-1]) {
thirdBefore = right;
}
}
return maxCount;
}
作者：meirikele
链接：https://leetcode.cn/problems/fruit-into-baskets/solution/by-meirikele-qpqu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
（2）这道题是最大覆盖字串，和最小覆盖子串的区别
力扣
