-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
930.py
53 lines (50 loc) · 1.56 KB
/
930.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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
__________________________________________________________________________________________________
sample 264 ms submission
class Solution:
def numSubarraysWithSum(self, A: List[int], S: int) -> int:
ones = []
cur = 0
for num in A:
if num == 0:
cur += 1
else:
ones.append(cur)
cur = 0
ones.append(cur)
if S == 0:
res = 0
for ele in ones:
res += (ele + 1) * ele //2
return res
L = len(ones)
if L < S + 1:
return 0
start = 0
ed = S
res = 0
while ed < L:
res += (ones[start] + 1) * (ones[ed] + 1)
ed += 1
start += 1
return res
__________________________________________________________________________________________________
sample 13992 kb submission
class Solution(object):
def numSubarraysWithSum(self, A, S):
i_lo = i_hi = 0
sum_lo = sum_hi = 0
ans = 0
for j, x in enumerate(A):
sum_lo += x
while i_lo < j and sum_lo > S:
sum_lo -= A[i_lo]
i_lo += 1
sum_hi += x
while i_hi < j and (
sum_hi > S or sum_hi == S and not A[i_hi]):
sum_hi -= A[i_hi]
i_hi += 1
if sum_lo == S:
ans += i_hi - i_lo + 1
return ans
__________________________________________________________________________________________________