# Python Simple (Prefix sum)

• Since we are interested in quantities of the form A[L] + A[L+1] + ... + A[R], let's use a standard technique of keeping a prefix sum P[i] = sum(A[:i]), so that we can quickly query A[L] + A[L+1] + ... + A[R] = P[R+1] - P[L].

Now, we would like to know if P[R+1] - P[L] = 0 (mod k) is solvable with 0 <= L < R < len(A). This means: For any 0 <= L < len(A), we would like to know if there is some L + 2 <= X < len(A) with P[X] = P[L].

This can be solved in linear time: at decreasing time i, we've now seen in total all elements in P[i+2:], and we want to know if P[i] is something we've seen before. If we have, then indeed P[i] = P[j] for j >= i + 2 as desired.

Of course, there is the pesky "mod k" part. When k is zero, the modulus should be ignored, otherwise we should consider values of P modulo abs(k).

``````def checkSubarraySum(self, A, k):
P = [0] #P[i] = sum(A[:i]), mod abs(k) if k != 0
for x in A:
v = P[-1] + x
if k: v %= abs(k)
P.append(v)

seen = set()
for i in xrange(len(P) - 3, -1, -1):