Problem:

Given a list ofnon-negativenumbers and a targetintegerk, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple ofk, that is, sums up to n*k where n is also aninteger.

Example 1:

Input:
 [23, 2, 4, 6, 7],  k=6

Output:
 True

Explanation:
 Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input:
 [23, 2, 6, 4, 7],  k=6

Output:
 True

Explanation:
 Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Solution:

1. create prefix sum array again. With S[0] = 0
2. use a Map<S[i] % k, i>, here key is "S[i] % k", value is index
   1. when S[i] % k is in the hashmap, check to see if i - dictionary[ S[i] % k ] >= 2, then return
   2. if S[i] % k not in map, add it in
3. Note, need to separate k = 0 out for a different discussion because divide by zero error

Time: O(n)

Space: O(k)

def checkSubarraySum(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: bool
    """
    n = len(nums)
    if k == 0:
        for i in range(n-1):
            if nums[i] == 0 and nums[i+1] == 0:
                return True
        return False

    # hash map to have one pass
    preSums = [0] * (n+1)
    dic = {0:0}
    for i in range(n):
        preSums[i+1] = preSums[i] + nums[i]
        target = preSums[i+1] % k
        if target in dic:
            if i+1 - dic[target] >= 2:
                return True
        else:
            dic[target] = i+1

    return False