deepSWE.io

Subarray Sum Equals K

Hashing

25 min

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

Example 1:

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

Output: 2

Solution (Prefix Sum & Hash Map)

This problem can be solved efficiently using a hash map that stores prefix sums and their frequencies.

Algorithm Steps

Initialize a hash map `prefixSums` with {0: 1} to handle subarrays that start from the beginning.
Initialize `count` and `currentSum` to 0.
Iterate through the array. In each iteration, add the current number to `currentSum`.
Calculate the difference `diff = currentSum - k`.
If `diff` is in `prefixSums`, it means there are subarrays ending at the current position with a sum of `k`. Add the frequency of `diff` to `count`.
Increment the frequency of `currentSum` in the `prefixSums` map.
After the loop, `count` will hold the total number of subarrays.

Nums:k:

Prefix Sum Map

Sum 0: Freq 1

Count

Current Sum: 0

Start with a prefix sum map {0: 1} to handle subarrays starting from index 0.

Subarray Sum Equals K Solution


class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        res = 0
        curSum = 0
        prefixSums = { 0 : 1 }
        
        for n in nums:
            curSum += n
            diff = curSum - k
            
            res += prefixSums.get(diff, 0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
            
        return res