力扣-数组-滑动窗口

 1 class Solution(object):
 2     def minSubArrayLen(self, target, nums):
 3         """
 4         :type target: int
 5         :type nums: List[int]
 6         :rtype: int
 7         """
 8         # 暴力求解 时间复杂度是n方 容易超时
 9         # 采用滑动窗口（本质与双指针相似），因为寻找的是连续子数组所以可以滑动解决
10         i = 0
11         n = len(nums)
12         res = n+1
13         sumarr = 0
14         for j in range(n): # 只遍历窗口end
15             sumarr += nums[j]
16             while sumarr>=target: # 窗口和符合条件时，窗口start向前，缩短窗口
17                 res = min(res, j-i+1)
18                 sumarr -= nums[i]
19                 i += 1
20         if res==n+1:
21             return 0
22         else:
23             return res

 1 class Solution(object):
 2     def totalFruit(self, fruits):
 3         """
 4         :type fruits: List[int]
 5         :rtype: int
 6         """
 7         # 考虑用滑动窗口解决
 8         cnt = Counter() # 计数器，是字典的子类
 9         res = 0
10         left = 0
11         for right in range(len(fruits)):
12             # 往篮子里放
13             cnt[fruits[right]] += 1
14             while len(cnt)>2:
15                 # 篮子里多于两种水果，left向前
16                 # 篮子里最多有三种水果
17                 cnt[fruits[left]] -= 1
18                 if cnt[fruits[left]] == 0:# 当left指向的水果在篮子中没了
19                     cnt.pop(fruits[left]) # 删除篮子对left水果的计数
20                 left += 1
21             res = max(res, right-left+1)
22         
23         return res