Subarray Sum Equals k II

problem at: https://www.lintcode.com/problem/subarray-sum-equals-k-ii

# Solution

Different from previous problem subarray sum equals k which asks for total number, this problems asks for min size.

Similar as previous problem subarray sum equals k which fails for squared time, we will just explore the linear time solution.

# HashMap (linear time)

Different from vanilla HashMap which stores mappings from prefix sum to count, here we need to store prefix sum to index instead.

Note that HashMap hm is initialized w/ {0:-1} to handle the sum(nums)==k case.

def subarraySumEqualsKII(self, nums, k):
    n = len(nums)
    hm = {0:-1}
    res = sys.maxsize
    csum = 0

    for i in range(n):
        csum += nums[i]
        if csum-k in hm:
            res = min(res, i-hm[csum-k])
        hm[csum] = i
    return res if res!=sys.maxsize else 1