前言

很久没做题了，久违的简单题，却没想到花了我一个小时我是一个一个一个究极菜狗啊啊，好久没做，思路都不清晰了，特记该文章边做题边理清思路

题目

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

来源：力扣（LeetCode）水果篮子
示例 1：

1
2
3
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

1
2
3
4
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

解题思路

滑动窗口，也就是双指针

给了数组，需要返回子数组最大符合长度

确定变量

快指针：int fast=0

慢指针：int slow=0

由题目可知：

明确判断点：是否满足一个最大数组长度 与 篮子存放的两种苹果种类的异同

需要记录两种苹果变量（动态的）

第一种：int first=0

第二种：int second=0

给出了果树的数组fruits

第一种类与慢指针绑定

第二种类与快指针绑定

first=fruits[fast];

second=fruits[slow];

最长数组计算:

fast-slow+1

需要返回的最大数组定义

int length=0;

列出情况

  1. 快指针指向的果树等于第一种
  2. 快指针指向的果树等于第二种
  3. 快指针指向的果树没有一种相等

三种情况，实际上是两种处理方式

1与2的可以合并一种情况处理，有一个条件满足即可:

1
2
3
4
5
6
if(fruits[fast]) == first || fruits[fast] == second){
  
    //更新返回长度
   	length = max(fast-slow+1, length)
     fast++;//快指针加一，慢指针不动
}

其他（就是出现情况三）：

1
2
3
4
5
6
7
8
9
10
11
12
else{
    //更新摘取果树顺序
    slow=fast-1;//slow回退fast一格,此时的快指针指向的值一定不等于slow的指向
    second=fruits[slow];//将该值的给第二种果树篮子
    frist=fruits[fast];//当前指向的值给第一种果树篮子
    //前方每有一个与第二种种类相同的果树，慢指针回退一个
    //避免slow=-1 再加上条件
	while(fruits[slow-1] == second && slow >= 1 )slow--;
    //更新返回长度
   	length = max(fast-slow+1, length);
    
}

总体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int slow = 0;
        int fast = 0;
        int first = fruits[fast];
        int second = fruits[slow];
        int length = 0;
        while(fast < fruits.size()){
            if(fruits[fast] == first || fruits[fast] == second){
                length = max(fast - slow + 1, length);
                fast++;
            }else{
                slow = fast - 1;
                second = fruits[slow];
                first = fruits[fast];
                while(slow >= 1 && fruits[slow - 1] == second) slow--;
                length = max(fast - slow + 1, length);
            }
        }
        return length;
    }
};

别看有两个while时间复杂度实际上是$O(n)$，时间复杂度主要还是看操作次数。