Python Simple (Prefix sum)


  • 7

    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):
            seen.add(P[i+2])
            if P[i] in seen:
                return True
        return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.