首页 > 代码库 > Leetcode 209. Minimum Size Subarray Sum

Leetcode 209. Minimum Size Subarray Sum

2024-09-02 19:14:26   220人阅读

思路一： 本题nums里面的数由于都是正数，所以可以用两个指针 start 和 end = 0。end++向后寻找，直到 start和end之间的sum>=s。例如 nums = [2, 3, 1, 2, 4, 3], s = 7。这一步结束时找到了start = 0 的最短的满足条件的subarray。

技术分享

显然当前的这个解可能不是以end = 3的最优解，所以start++，直到total < 7。

技术分享

这时我们又需要end++，直到total>=s来寻找以start = 1开头的最短subarray。

 1 class Solution(object):
 2     def minSubArrayLen(self, s, nums):
 3         """
 4         :type s: int
 5         :type nums: List[int]
 6         :rtype: int
 7         """
 8         size = len(nums)
 9         if size == 0:
10             return 0
11         left = right = 0
12         total = 0
13         res = size + 1
14         
15         while right < size:
16             while total < s and right < size:
17                 total += nums[right]
18                 right += 1
19             while left < right and total >= s:
20                 res = min(res, right - left)
21                 total -= nums[left]
22                 left += 1
23                 
24         return res if res <= size else 0

 

Leetcode 209. Minimum Size Subarray Sum


联系
我们