总和等于一个数字的子串没有导入

Question

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

我使用了这段似乎有效的代码。我有一个 1 秒的超时，这段代码在几毫秒的测试中失败了，其中包含很长的数字字符串（比如 10000 次 1）。我该如何优化它？（没有导入！！）

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

int_seq='3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2' 和小计 = 9

输出=7

Answer 1

你有一个二次解。听起来您需要一个线性的解决方案。这里有一个简短的提示，因为你真的应该自己解决这个问题。

尝试创建一个累加和 accumulate，使得 accumulate[i] 是包括 i 在内的所有元素的总和。现在对于每个索引 i 和元素 accumulate[i]，您需要找出有多少索引 j > i 使得 accumulate[j] == accumulate[i] + subtotal。（提示，您需要将字典映射值累积到它们的索引中）。

可能有更好的解决方案，但这是第一个想到的。

总和等于一个数字的子串没有导入

substrings with sum equals to a number without import

python

string

substring