-
Notifications
You must be signed in to change notification settings - Fork 2
/
q1546.py
31 lines (28 loc) · 837 Bytes
/
q1546.py
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
#!/usr/bin/python3
from typing import List
class Solution:
def maxNonOverlapping(self, nums: List[int], target: int) -> int:
dic = {0:-1}
start = -1
presum = 0
result = 0
for i in range(len(nums)):
num = nums[i]
presum += num
remain = presum - target
if remain in dic and dic[remain] >= start:
result += 1
start = i
dic[presum] = i
return result
def maxNonOverlapping2(self, nums: List[int], target: int) -> int:
dic = {0:0}
sum = 0
result = 0
for num in nums:
sum += num
remain = sum - target
if remain in dic:
result = max(result, dic[remain] + 1)
dic[sum] = result
return result