Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 3/24/2019:
- 第二遍做这道题,想的明白点儿了。O(n)的解法
- 还是用一个queue来维护这个窗口,然后用一个值 subSum 来维护queue中的值的和。
- 用一个while循环,每次遍历到一个值就把他加到queue里面,同时加到subSum中。在每次遍历一次以后要再加一个while循环从queue的左侧pop值,知道subSum小于给定的值位置。重复这个过程
- """
- class Solution:
- def minSubArrayLen(self, s: int, nums: List[int]) -> int:
- if not nums:
- return 0
- r = 0
- q = collections.deque()
- subsum = 0
- size = sys.maxsize
- while r < len(nums):
- subsum += nums[r]
- q.append(nums[r])
- r += 1
- while subsum >= s:
- size = min(size, len(q))
- tmp = q.popleft()
- subsum -= tmp
- return size if size != sys.maxsize else 0
- """
- 209. Minimum Size Subarray Sum
- 这道题其实想的不太透彻。最初的想法是既然是让你找一个连续的subarray,而这个subarray更像是一个窗口,所以依据之前的经验来想的话直接想到的是用
- 1)queue来做这件事儿,
- 2)需要create一个variable来记录sum,每推进去一个值,sum累加这个值。
- 3)需要一个最大值记录最小的queue的size,这个queue的size就是最后要返回的值
- 当sum大于等于给的目标值时,如果sum - queue[0]大于s的话就尝试着从queue的前面pop值,每次pop之前求一下queue的长度,记录到最小值里面。最后返回时
- 要比较res是否还是最大值,如果是最大值说明遍历了整个array,还是没有找到subarray的sum大于s的。
- """
- from collections import deque
- import sys
- class Solution:
- def minSubArrayLen(self, s: 'int', nums: 'List[int]') -> 'int':
- if not nums:
- return 0
- res = sys.maxsize
- tmp = 0
- idx = 0
- q = deque()
- while idx < len(nums):
- while tmp < s and idx < len(nums):
- tmp += nums[idx]
- q.append(nums[idx])
- idx += 1
- while tmp >= s:
- res = min(res, len(q))
- tmp -= q[0]
- q.popleft()
- return 0 if res == sys.maxsize else res
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement