jinhuang1102

209. Minimum Size Subarray Sum

Feb 19th, 2019
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.44 KB | None | 0 0
  1. """
  2. 3/24/2019:
  3. 第二遍做这道题,想的明白点儿了。O(n)的解法
  4. 还是用一个queue来维护这个窗口,然后用一个值 subSum 来维护queue中的值的和。
  5. 用一个while循环,每次遍历到一个值就把他加到queue里面,同时加到subSum中。在每次遍历一次以后要再加一个while循环从queue的左侧pop值,知道subSum小于给定的值位置。重复这个过程
  6. """
  7. class Solution:
  8.     def minSubArrayLen(self, s: int, nums: List[int]) -> int:
  9.         if not nums:
  10.             return 0
  11.        
  12.         r = 0
  13.         q = collections.deque()
  14.         subsum = 0
  15.         size = sys.maxsize
  16.        
  17.         while r < len(nums):
  18.             subsum += nums[r]
  19.             q.append(nums[r])
  20.             r += 1
  21.            
  22.             while subsum >= s:
  23.                 size = min(size, len(q))
  24.                 tmp = q.popleft()
  25.                 subsum -= tmp
  26.            
  27.         return size if size != sys.maxsize else 0
  28.  
  29.  
  30.  
  31.  
  32.  
  33. """
  34. 209. Minimum Size Subarray Sum
  35.     这道题其实想的不太透彻。最初的想法是既然是让你找一个连续的subarray,而这个subarray更像是一个窗口,所以依据之前的经验来想的话直接想到的是用
  36.     1)queue来做这件事儿,
  37.     2)需要create一个variable来记录sum,每推进去一个值,sum累加这个值。
  38.     3)需要一个最大值记录最小的queue的size,这个queue的size就是最后要返回的值
  39.     当sum大于等于给的目标值时,如果sum - queue[0]大于s的话就尝试着从queue的前面pop值,每次pop之前求一下queue的长度,记录到最小值里面。最后返回时                      
  40.    要比较res是否还是最大值,如果是最大值说明遍历了整个array,还是没有找到subarray的sum大于s的。
  41. """
  42. from collections import deque
  43. import sys
  44.  
  45. class Solution:
  46.     def minSubArrayLen(self, s: 'int', nums: 'List[int]') -> 'int':
  47.         if not nums:
  48.             return 0
  49.                
  50.         res = sys.maxsize
  51.         tmp = 0
  52.         idx = 0
  53.         q = deque()
  54.        
  55.        
  56.         while idx < len(nums):
  57.             while tmp < s and idx < len(nums):
  58.                 tmp += nums[idx]
  59.                 q.append(nums[idx])
  60.                 idx += 1
  61.                
  62.             while tmp >= s:
  63.                 res = min(res, len(q))
  64.                 tmp -= q[0]
  65.                 q.popleft()
  66.                
  67.         return 0 if res == sys.maxsize else res
Advertisement
Add Comment
Please, Sign In to add comment