Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一个数列,问其中最少多少个连续元素之和可以大于target,预处理前缀和,然后二分答案判断是否可行,复杂度O(nlogn)


 1 #209
 2 #Runtime: 241 ms (Beats 10.50%)
 3 #Memory: 24.1 MB (Beats 5.56%)
 4 
 5 class Solution(object):
 6     def minSubArrayLen(self, target, nums):
 7         """
 8         :type target: int
 9         :type nums: List[int]
10         :rtype: int
11         """
12         pre_sum = [0]
13         for i in range(0, len(nums)):
14             pre_sum.append(pre_sum[-1] + nums[i])
15         if pre_sum[-1] < target:
16             return 0
17         l, r = 1, len(pre_sum)
18         while l < r:
19             mid = (l + r) // 2
20             ok = False
21             for i in range(mid, len(pre_sum)):
22                 if pre_sum[i] - pre_sum[i - mid] >= target:
23                     ok = True
24                     break
25             if ok:
26                 r = mid
27             else:
28                 l = mid + 1
29         return r

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理