sum等于数字的子字符串

Question

我有一个字符串S='n1，n2，n3.nk‘(例如’3，0，4，0，3，1，0，1，0，1，0，1，0，0，5，0，4，2‘)和一个数字m= S (es 9)。我想知道有多少个sum等于m的子串。

我使用了这段代码，它似乎是有效的。我有一个1秒的超时时间，这段代码在很长的数字串测试中失败了几毫秒。我该如何优化它呢？

m = 9
numbers = list(map(int,S.split(",")))
result  = 0
sums    = numbers
for i in range(len(numbers)):
    result += sums.count(m)
    sums   = [a+b for a,b in zip(sums,numbers[i+1:]) ]
print(result)``` 

Answer 1

m = 9

c = 0
for i in range(len(numbers)):
    for j in range(len(numbers)-i):
        sum = 0
        for k in numbers[i:i+j]:
            sum += k
            if sum == m:
                c += 1
            if sum > m: # strict >, thanks to Tim Roberts
                break

print(c)

Answer 2

一个计算前缀和的O(n)解。例如，如果前缀总和是13，那么要得到9，您需要减去前缀总和4，因此请查看前缀总和4出现的频率：

from collections import Counter

S = '3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
m = 9

numbers = map(int, S.split(","))
result = 0
presum = 0
presums = Counter([presum])
for number in numbers:
    presum += number
    result += presums[presum - m]
    presums[presum] += 1

print(result)

也适用于负数。