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 ( like 10000 times 1). How could I optimize it? (no import !!)

def ex1(int_seq, subtotal):
    list_numbers = list(map(int,int_seq.split(",")))
    c = 0
    count_number = list_numbers
    for i in range(len(list_numbers)):
        c  = count_number.count(subtotal)
        count_number= [a b for a,b in zip(count_number,list_numbers[i 1:]) ]
    return c

with int_seq='3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2' and subtotal = 9

output = 7

CodePudding user response：

You have a quadratic solution. It sounds like you need a solution that is linear. Here's a brief hint, because you really should solve this yourself.

Try creating a cumulative sum accumulate such that accumulate[i] is the sum of all the elements up to and including i. Now for each index i and element accumulate[i], you need to find how many indexes j > i are there such that accumulate[j] == accumulate[i] subtotal. (Hint, you'll need do keep a dictionary mapping values in accumulate to their index).

There may be better solutions, but that's the first that comes to mind.