Subarray Sum Equals K

Problem Statement

You’re a sum seeker with an array of integers and a target k. How many contiguous subarrays sum to k? This medium-level hashing challenge is a prefix-sum party—use a map to tally those matches!

Example

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

Output: 2 ([1,1], [1,1])

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

Output: 2 ([1,2], [3])

Input: nums = [1, -1, 0], k = 0

Output: 3 ([1,-1], [1,-1,0], [0])

Code

public class Solution {
    public int subarraySum(int[] nums, int k) {
        Map sumFreq = new HashMap<>();
        sumFreq.put(0, 1); // Empty subarray
        int sum = 0, count = 0;
        for (int num : nums) {
            sum += num;
            count += sumFreq.getOrDefault(sum - k, 0);
            sumFreq.put(sum, sumFreq.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
            

from collections import defaultdict
def subarray_sum(nums, k):
    sum_freq = defaultdict(int)
    sum_freq[0] = 1
    curr_sum, count = 0, 0
    for num in nums:
        curr_sum += num
        count += sum_freq[curr_sum - k]
        sum_freq[curr_sum] += 1
    return count
            

function subarraySum(nums, k) {
    let sumFreq = new Map([[0, 1]]);
    let sum = 0, count = 0;
    for (let num of nums) {
        sum += num;
        count += (sumFreq.get(sum - k) || 0);
        sumFreq.set(sum, (sumFreq.get(sum) || 0) + 1);
    }
    return count;
}
            

Explanation

• Hashing Insight: Track cumulative sums; if sum-k exists, a subarray sums to k.
• Flow: Update running sum, check map for sum-k, increment its freq.
• Example Walkthrough: [1,1,1], k=2 → sums=1,2,3, map={0:1,1:1,2:1,3:1}, count=2.
• Key Detail: sumFreq[0]=1 handles subarrays starting at index 0.
• Negatives: Works with negative numbers seamlessly.

Note