我有一個字串 S='n1,n2,n3.......nk'（例如'3,0,4,0,3,1,0,1,0,1,0,0,5, 0,4,2') 和一個數 m= S (es 9)。我想知道有多少個總和等于 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)```
uj5u.com熱心網友回復：
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)
uj5u.com熱心網友回復：
計算前綴和的 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)
也適用于負數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/335424.html