209 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回0。
示例：

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶：

• 如果你已经完成了时间复杂度的解法，请尝试时间复杂度的解法。

什么叫子数组？

如果没有解怎么办？ 返回 0

• 暴力法：
  • 遍历所有的连续子数组[i…j]
  • 计算其和sum，验证sum≥s
  • 时间复杂度为
  • 优化暴力解：
• 滑动窗口
  • 两个指针 left 和 right，left 代表滑窗的左边框，right 代表滑窗的右边框。
  • 两者通过分别向右滑动，前者能使窗口之间的和减小，后者能使窗口之间的和增大。
  • 开始时二者重合，窗口的和就是重合点所在的数。
  • 1. right 向右滑动，使和变大。当恰好大于等于s时，记录滑窗所包括的子数组长度ans，若ans已有数值，需判断新值是否小于旧值，若是，更新ans。
  • 1. left 向右滑动，判断是否仍大于等于s。
  • 1. 若是，重复步骤2；若否，更新ans并转步骤1。直到右边框到达最右边。
• 【2 3 1 2 4 3】 s = 7
  • start
  • left=0 right=0 sum=2
  • left=0 right=1 sum=5
  • left=0 right=2 sum=6
  • left=0 right=3 sum=8 ans=4
  • left=1 right=3 sum=6
  • left=1 right=4 sum=10
  • left=2 right=4 sum=7 ans=3
  • left=3 right=4 sum=6
  • left=3 right=5 sum=9
  • left=4 right=5 sum=7 ans=2
  • end

    class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
       i, j, r =0, 0, len(nums) + 1
       sums = []
       for num in nums:
           if not sums:
               sums.append(num)
           else:
               sums.append(sums[-1] + num)
       while i < len(nums) and j < len(nums):
           if sums[j] - sums[i] + nums[i] < s:
               j += 1
           else:
               if j + 1 - i < r:
                   r = j + 1 - i
               i += 1
       if r != len(nums) + 1:
           return r
       else:
           return 0