substrings with sum equals to a number-CodePudding

I have a string S='n1,n2,n3.......nk' (ex'3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2') and a number m= S (es 9). I want to know how many substrings with sum equals m there are.

I used this code which seems to work. I have a 1 second timeout and this code fails a few milliseconds test with very long strings of numbers. How could I optimize it?

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)```

CodePudding user response：

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)

CodePudding user response：

An O(n) solution counting prefix sums. For example if a prefix sum is 13, then to get to 9, you want to subtract prefix sum 4, so look up how often prefix sum 4 occurred:

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)

Works with negative numbers as well.