难度：★★★☆☆
类型：数组
方法：滑动窗口

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。

用这个程序你能收集的水果树的最大总量是多少？

示例 1：

输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。

示例 2：

输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

示例 3：

输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。

示例 4：

输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。

提示：

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

解答

题目说了那么多，实际上要求就一个：

给定一个数组，求只包含两种元素的最长连续子序列。

连续子序列的问题常常使用滑动窗口来解决，使用双指针（左指针left和右指针right）定义滑动窗口。

我们使用一个字典来记录当前滑动窗口中的苹果种类及其对应数量，每当右指针右移，就会遇到一个新的苹果，将其添加到篮子中，一旦篮子中苹果的种类超过两种，我们需要把左指针右移，直到篮子里苹果种类保持在2种。

右指针遍历到整个数组最右端为止，在此过程中及时记录当前子数组的最大长度。

class Solution:
    def totalFruit(self, tree) -> int:

        left, right = 0, 0                  # 左右指针
        basket = dict()                     # 篮子里的苹果种类及其数量
        fruit_type = 0                      # 篮子中的苹果类别数
        res = 0                             # 结果

        while right < len(tree):            # 下标合法时执行
            apple_right = tree[right]       # 获取当前苹果
            right += 1                      # 右指针右移

            if apple_right not in basket:   # 只要出现新的苹果种类，更新一下篮子
                basket[apple_right] = 1
                fruit_type += 1
            else:                           #
                basket[apple_right] += 1

            while fruit_type > 2:
                apple_left = tree[left]
                left += 1
                if basket[apple_left] > 0:
                    basket[apple_left] -= 1
                if basket[apple_left] == 0:
                    del basket[apple_left]
                    fruit_type -= 1

            res = max(res, right - left)

        return res

我们可以使用defaultdict类来简化代码，这个类的好处是在没有键时可以有默认值，而不会因为找不到这个键而报错。

from collections import defaultdict


class Solution:
    def totalFruit(self, tree) -> int:

        left, right = 0, 0                  # 左右指针
        basket = defaultdict(int)           # 篮子里的苹果种类及其数量
        res = 0                             # 结果

        while right < len(tree):            # 下标合法时执行
            apple_right = tree[right]       # 获取当前苹果
            right += 1                      # 右指针右移
            basket[apple_right] += 1        # 把这个苹果装进篮子

            while len(basket) > 2:          # 一旦出现篮子中苹果种类超过两种
                apple_left = tree[left]     # 左侧苹果
                left += 1                   # 左指针右移
                basket[apple_left] -= 1     # 把该苹果从篮子里扔出去
                if basket[apple_left] == 0: # 篮子里没有这种苹果了
                    del basket[apple_left]  # 从篮子里删掉这种苹果的记录

            res = max(res, right - left)    # 更新一下结果

        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析