209. 长度最小的子数组

Medium

方法一(双指针,滑动窗口)

思路

应为题目中要求的连续的子数组,想到可以使用双指针滑动窗口的方式来求解,这样遍历的范围都是连续的子数组

尝试写一下代码,AC!

代码

python3

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i = 0
        j = 1
        min_length = math.inf
        while j <= len(nums):
          if sum(nums[i:j]) < s:
            j += 1
          else:
            while sum(nums[i:j]) >= s:
              min_length = min(min_length, j - i)
              i += 1

        return 0 if min_length == math.inf else min_length

方法二(前缀和)

思路

尝试写一下代码,AC!

个人觉得,还是滑动串口的方法更容易想到

代码

python3

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
      presum = [0]
      sum = 0
      ans = math.inf
      for i in nums:
        sum += i
        presum.append(sum)
      for k in range(1, len(presum) + 1):
        t = s + presum[k - 1]
        closest_index = bisect.bisect_left(presum, t)
        if closest_index <= len(nums):
          ans = min(ans, closest_index - k + 1)
      return 0 if ans == math.inf else ans