classSolution: defminSubArrayLen(self, target: int, nums: List[int]) -> int: n = len(nums) ans = n + 1# 也可以写 inf s = left = 0 for right, x inenumerate(nums): # 枚举子数组右端点 s += x while s >= target: # 满足要求 ans = min(ans, right - left + 1) s -= nums[left] left += 1# 左端点右移 return ans if ans <= n else0 # 滑动窗口,本解法可戏称为蜗牛蠕动法 # 双指针滑窗,考虑本题target都为正整数,将右指针右移,则sum一直增大,若减去左指针数后仍然大于等于target,则左指针右移。
classSolution: deffindMaxAverage(self, nums: List[int], k: int) -> float: max_sum = -inf window_sum = 0 for right, num inenumerate(nums): window_sum += num
left = right - k + 1 if left < 0: continue max_sum = max(max_sum, window_sum) window_sum -= nums[left] return max_sum/k
解法2-灵茶山艾府
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution: deffindMaxAverage(self, nums: List[int], k: int) -> float: max_s = -inf # 窗口元素和的最大值 s = 0# 维护窗口元素和 for i, x inenumerate(nums): # 1. 进入窗口 s += x if i < k - 1: # 窗口大小不足 k continue # 2. 更新答案 max_s = max(max_s, s) # 3. 离开窗口 s -= nums[i - k + 1] return max_s / k