Subarray Sum Equals K

Problem Statement: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

Source: https://leetcode.com/problems/subarray-sum-equals-k/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon   Netflix Google

Code:

    def subarraysum(self, nums, k):
        """
        nums: List[int]
        k: int
        return: int
        """
        
        prefix_cnt={0:1}
        summ=0
        result=0
        
        for i in nums:
            summ+=i
            
            if summ-k in prefix_cnt:
                result+=prefix_cnt[summ-k]
            
            if summ in prefix_cnt:
                prefix_cnt[summ]+=1
            else:
                prefix_cnt[summ]=1
            
        return result 

Thought Process / Explanation:

Hints to use prefix sum because of finding subarray of sum k. Because if Prefix[i]-Prefix[j] == 0 then i+1 to j in original array sums to ZERO. Here instead of 0, we have been given K. And overall since we need to return the count of such subarrays.. so probably using some dict.

Thank You!