# Find an array slice equaling sum

I would like to be reviewed on efficiency, style, and obviously if there is a bug I would like to know.

def findsum(a, n):
''' Find whether a consecutive array slice sums up to n '''
for i in range(len(a)):
j = i + 1
while j <= len(a):
if sum(a[i:j]) == n:
return True
j += 1
return False


1. There's a bug:

>>> a = [1, 2, 3]
>>> findsum(a, 0)
False


but the result should be True because the consecutive slice a[0:0] sums to zero.

2. The docstring could be clearer. "a consecutive array slice" — of which array? Presumably the parameter a is meant, but it is best to be explicit. Similarly, "Find whether" — and then what? The docstring should say what value is returned.

3. The function has runtime $Θ(n^3)$. That's because sum(a[i:j]) takes an unnecessary copy of the slice, and because it sums it starting at the beginning of the slice. But if you maintained a running sum, then the runtime would come down to $Θ(n^2)$. That's easy to implement using itertools.accumulate and itertools.islice:

from itertools import accumulate, islice

def findsum(a, n):
"""Return True if any consecutive slice of the sequence a sums to n,
False if none do.

"""
return n == 0 or any(total == n
for i in range(len(a))
for total in accumulate(islice(a, i, None)))