-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path209_minSubArrayLen.py
More file actions
56 lines (46 loc) · 1.48 KB
/
209_minSubArrayLen.py
File metadata and controls
56 lines (46 loc) · 1.48 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from bisect import bisect_left
from typing import List
class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
ans = len(nums) + 1
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total = sum(nums[i: j + 1])
if total >= s:
ans = min(ans, j - i + 1)
return ans if ans < len(nums) + 1 else 0
def min_subarray_len(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1
sums = [0]
for i in range(n):
sums.append(sums[-1] + nums[i])
for i in range(1, n + 1):
target = s + sums[i - 1]
bound = bisect_left(sums, target)
if bound != len(sums):
ans = min(ans, bound - (i - 1))
return 0 if ans == n + 1 else ans
def min_subarray_len_2(self, s: int, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
ans = n + 1
start, end = 0, 0
total = 0
while end < n:
total += nums[end]
while total >= s:
ans = min(ans, end - start + 1)
total -= nums[start]
start += 1
end += 1
return 0 if ans == n + 1 else ans
if __name__ == '__main__':
s = 7
nums = [2, 3, 1, 2, 4, 3]
solution = Solution()
print(solution.min_subarray_len_2(s, nums))