Posted on 2023-07-07 00:27
Uriel 阅读(31)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code 、
二分.三分
给定一个数列，问其中最少多少个连续元素之和可以大于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