力扣-数组-滑动窗口

题目顺序

209长度最小的子数组，904水果成篮

解题思路

1.滑动窗口求解的题目中，关键词为”求解连续“

2.暴力解法是双重for循环，相当于对滑动窗口的起始和终止点都遍历

3.滑动窗口求解是，只遍历终止点，当sum符合条件时，start++，向前一步缩小窗口

4.终止条件是终止点end遍历完

 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

# 本题是最小滑动窗口，所以当符合条件时，还要缩短窗口，start向前；不符合条件时，right向前遍历

 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

# 本题是最大滑动窗口，当符合条件时，即篮子里有两种水果，求最大水果个数，然后right继续遍历；否则left向前直到符合条件，求最大水果个数，right继续遍历。