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].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

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

Solutions:
class Solution:

	def subarraySum(self, nums, k):
		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):
		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):
		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):
		(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):
		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):
		(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):
		count = collections.Counter()
		count[0] = 1
		ans = su = 0
		for x in nums:
			su += x
			ans += count[su - k]
			count[su] += 1
		return ans