leetcode-hashmap

560. Subarray Sum Equals K.py

class Solution(object):
    """        
    Prfix sum+Hashmap
        公式推導:
        range(i,j) = range(0,j)-range(0,i) where j > i
        ->range(i,j)-k = range(0,j)-range(0,i)-k
        we're looking for range(i,j)-k == 0
        So, when we keep track of number of prefix sum in hashmap
        So, if range(0,j)-k in hashmap, number of range(i,j)-k ==0 is eqaul to number of range(0, i)

    """
    def subarraySum(self, A: List[int], k: int) -> int:
          cum_sum = 0
          # to handle case range(i,j)-k==0 and i=0 and j > i
          count = collections.defaultdict(int)
          count[0]=1
          ans = 0
          for a in A:
              cum_sum+=a
              key = cum_sum-k 
              if key in count:
                  ans+=count[key]
              count[cum_sum]+=1
          return ans