如何计算一个字符串中包含的子字符串和的次数?

Question

这是字符串和小计:int_seq='3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'

subtotal = 9

所以函数必须返回7，这就是为什么:

3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
__'0,4,0,3,1,0,1,0'_____________
__'0,4,0,3,1,0,1'_______________
____'4,0,3,1,0,1,0'_____________
____'4,0,3,1,0,1'_______________
____________________'0,0,5,0,4'_
______________________'0,5,0,4'_
________________________'5,0,4'_

我真正不明白的很可能是如何使用for，而且，我不能使用外部库。

Answer 1

您可以跟踪起始点(索引)和从该起始点开始的累积和。每次累积的总和达到或超过目标时，你就向前移动起点，减去旧的值，直到总和回到目标以下。在此过程中，每次累积和等于目标时，您就有一个可以计数的合格子字符串。

然而，除非我们考虑到零的影响，否则这不会完美地工作。例如，当我们得到[0,4,0,3,1,0,1,0,0,1]时，最后一个1使总和大于9所以我们移动起始位置得到[4,0,3,1,0,1,0,1]但它仍然大于9因为我们已经传递了倒数第二个零所以两个有效的子范围会被跳过。[4,0,3,1,0,1,0]和[4,0,3,1,0,1]。为了在保持线性性能的同时解决这个问题，我们需要在将最后一项添加到总和之前执行范围缩小，并在总和与目标匹配时为每个末尾的零计算一个额外的子范围。

S = '3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
target = 9
N = list(map(int,S.split(',')))
start  = 0
cumSum = 0
count  = 0
for end,value in enumerate(N+[target+1]): # force out ending subranges
while cumSum+value>target and start<end:
cumSum -= N[start]    # shrink range
start  += 1
if cumSum==target:    # count matches (+extra for trailing zeroes)
count += next((c for c,v in enumerate(N[end-1:start:-1],1) if v),1)
cumSum += value           # extend range
count  += cumSum==target  # count matches

print(count) # 7

如果您想确切地知道哪些子字符串产生目标和，您可以稍微更改循环以打印它们并获得它工作的证明:

S = '3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
target = 9
N = list(map(int,S.split(',')))
start  = 0
cumSum = 0
count  = 0
for end,value in enumerate(N+[target+1]): # force out ending subranges
while cumSum+value>target and start<end:
cumSum -= N[start]    # shrink range
start  += 1
if cumSum==target:    # count matches (+extra for trailing zeroes)
c = next((c for c,v in enumerate(N[end-1:start:-1],1) if v),1)
print([start,end],N[start:end],f"Matches {c}")
cumSum += value           # extend range
if cumSum==target:
print([start,end+1],N[start:end+1],"Matches 1")
[1, 8] [0, 4, 0, 3, 1, 0, 1] Matches 1
[1, 9] [0, 4, 0, 3, 1, 0, 1, 0] Matches 1
[2, 9] [4, 0, 3, 1, 0, 1, 0] Matches 2
[10, 15] [0, 0, 5, 0, 4] Matches 1
[11, 15] [0, 5, 0, 4] Matches 1
[12, 15] [5, 0, 4] Matches 1