904. 水果成篮

题目：你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
（1）你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
（2）一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

来源：力扣（LeetCode）
链接 https://leetcode.cn/problems/fruit-into-baskets

个人思路

1. 刚开始想着用动规，但没能构建出前后关系，然后想着模拟一下试试。
   首先使用nums列表记录要采摘的两种类型的果树，然后使用left和right两个分别标记当前遍历采摘中这两种水果最后出现的位置，当出现新的水果种类时，计算该次采摘的数量，然后把最后位置出现较远的水果类型去掉，更新要采摘的水果类型及位置。

class Solution:def totalFruit(self, fruits: List[int]) -> int:res = 0nums = []left,right = 0,0   # left为nums[0]的最后位置，right为nums[1]的最后位置count = 0   # 当前最大数量size = len(fruits)for i in range(size):# print(left,right,nums,count)if fruits[i] not in nums:# 开始状态if len(nums) < 2:# 出现第二种类型的果树时更新right的值if len(nums) == 1:right = inums.append(fruits[i])count += 1else:# 更新当前两种类型的果树nums[0] = fruits[left] if left > right else fruits[right]nums[1] = fruits[i]res = res if res > count else count# 前面已经遍历的nums[0]类型果树的数量count = abs(left - right) + 1left = max(left,right) right = ielse:if fruits[i] == nums[0]:left = ielse:right = icount += 1return res if res > count else count

复杂度分析

时间复杂度：O(n)只需一次遍历
空间复杂度：O(1)只需常数空间

官方思路

1. 滑动窗口，其实我上面的应该也是滑动窗口
   （1）我们可以使用滑动窗口解决本题，left 和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。
   （2）我们每次将right 移动一个位置，并将fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，并将 fruits[left] 从哈希表中移除，直到哈希表满足要求为止。
   （3）需要注意的是，将 fruits[left] 从哈希表中移除后，如果 fruits[left] 在哈希表中的出现次数减少为0，需要将对应的键值对从哈希表中移除。

class Solution:def totalFruit(self, fruits: List[int]) -> int:cnt = Counter()left = ans = 0for right, x in enumerate(fruits):cnt[x] += 1while len(cnt) > 2:cnt[fruits[left]] -= 1if cnt[fruits[left]] == 0:cnt.pop(fruits[left])left += 1ans = max(ans, right - left + 1)return ans

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/fruit-into-baskets/solution/shui-guo-cheng-lan-by-leetcode-solution-1uyu/
来源：力扣（LeetCode）