Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2



Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Difficulty: interview

Starter code:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        

Solutions:
class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         
         dic = {}
         numSum = 0
         dic[0] = 1
         ans = 0
         for i in range(len(nums)):
             numSum += nums[i]
             if (numSum - k) in dic:
                 ans += dic[numSum - k]
             if numSum in dic:
                 dic[numSum] += 1
             else:
                 dic[numSum] = 1
         return ans

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         cum_sum_dict = {}
         cum_sum_dict[0] = 1
         left_sum = 0
         count = 0
         for t in nums:
             left_sum = left_sum + t
             if (left_sum - k) in cum_sum_dict:
                 count = count + cum_sum_dict[left_sum - k]
             if left_sum in cum_sum_dict:
                 cum_sum_dict[left_sum] = cum_sum_dict[left_sum] + 1
             else:
                 cum_sum_dict[left_sum] = 1
         
         return count

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         l_nums = len(nums)
         c = 0
         state = dict()
         state[0] = 1
         sum = 0
         
         for idx in range(0, l_nums):
             sum += nums[idx]
             if((sum - k) in state):
                 c += state[sum - k]
             state[sum] = (state[sum] if sum in state else 0) + 1
         return c
     


class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         count, current, solution = {0: 1}, 0, 0
         for num in nums:
             current += num
             solution += count.get(current - k, 0)
             count[current] = count.get(current, 0) + 1
         return solution

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         sum_map = {0:1}
         count = 0
         total_sum = 0
         total = 0
         for numb in nums:
             total += numb
             count += sum_map.get(total-k, 0)
             sum_map[total] = sum_map.get(total, 0) +1
         return count

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         count, cur, res = {0: 1}, 0, 0
         for v in nums:
             cur += v
             res += count.get(cur - k, 0)
             count[cur] = count.get(cur, 0) + 1
         return res

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         count, current, solution = {0: 1}, 0, 0
         for num in nums:
             current += num
             solution += count.get(current - k, 0)
             count.update({current: count.get(current, 0) + 1})
         return solution

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         count, current, solution = {0: 1}, 0, 0
         for num in nums:
             current += num
             solution += count.get(current - k, 0)
             count.update({current: count.get(current, 0) + 1})
         return solution

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         count, current, solution = {0: 1}, 0, 0
         for num in nums:
             current += num
             solution += count.get(current - k, 0)
             count.update({current: count.get(current, 0) + 1})
         return solution

class Solution:
     def subarraySum(self, nums, k):
         """
         :type nums: List[int]
         :type k: int
         :rtype: int
         """
         # count = 0
         # for i in range(len(nums)):
         #     for j in range(i,len(nums)):
         #         if sum(nums[i:j+1]) == k:
         #             count += 1
         # return count
         
 #         count = 0
 #         s = 0
 #         cum_sum = []
 #         for x in nums:
 #             s += x
 #             cum_sum.append(s)
 #             if s == k:
 #                 count += 1
         
 #         for i,x in enumerate(cum_sum):
 #             for y in cum_sum[i+1:]:
 #                 if y - x == k:
 #                     count += 1
 #         return count
 
         # good answer @awice
         # time: O(n) space: O(1)
         # idea:count[V] is the number of previous prefix sums with value V. If our newest prefix sum has value W, and W-V == K,
         #   then we add count[V] to our answer.This is because at time t, A[0] + A[1] + ... + A[t-1] = W, 
         #   and there are count[V] indices j with j < t-1 and A[0] + A[1] + ... + A[j] = V. 
         #   Thus, there are count[V] subarrays A[j+1] + A[j+2] + ... + A[t-1] = K.
         count = collections.Counter()
         count[0] = 1
         ans = su = 0
         for x in nums:
             su += x
             ans += count[su-k]
             count[su] += 1
         return ans