Posted on 2023-07-07 00:27
Uriel 閱讀(67)
評論(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