Leetcode 930. Binary Subarrays With Sum

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Binary Subarrays With Sum

2. Solution

解析:Version 1暴力法,超时。Version 2,统计前i个元素和total出现的次数,S出现的次数等于每一个total - S出现的次数的和。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def numSubarraysWithSum(self, A, S):
n = len(A)
count = 0
for i in range(n):
total = A[i]
if total == S:
count += 1
for j in range(i + 1, n):
total += A[j]
if total > S:
break
if total == S:
count += 1
return count
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def numSubarraysWithSum(self, A, S):
n = len(A)
result = 0
total = 0
count = collections.Counter({0 : 1})
for i in range(n):
total += A[i]
result += count[total - S]
count[total] += 1
return result

Reference

  1. https://leetcode.com/problems/binary-subarrays-with-sum/
如果有收获,可以请我喝杯咖啡!