Meta — Subarray Sum Equals K (Prefix Sum + HashMap)

Problem (Meta Arrays Classic)

Given array nums and integer k, return the count of subarrays that sum to k.

Example:

nums = [1,1,1], k = 2 → 2
nums = [1,2,3], k = 3 → 2

Key Insight — Prefix Sum + HashMap

sum(i..j) = prefix[j] - prefix[i-1]

For sum(i..j) == k, we need prefix[j] - k == prefix[i-1].

Track frequency of prefix sums seen so far. For each new prefix sum, add freq[prefix - k] to result.

Solutions

Python

from collections import defaultdict

def subarraySum(nums, k: int) -> int:
    count = 0
    prefix = 0
    freq = defaultdict(int)
    freq[0] = 1
    for n in nums:
        prefix += n
        count += freq[prefix - k]
        freq[prefix] += 1
    return count

JavaScript

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

Java

import java.util.*;
public int subarraySum(int[] nums, int k) {
    Map<Integer,Integer> f=new HashMap<>(); f.put(0,1);
    int prefix=0, count=0;
    for (int n:nums){ prefix+=n; count+=f.getOrDefault(prefix-k,0); f.merge(prefix,1,Integer::sum); }
    return count;
}

C++

#include <unordered_map>
#include <vector>
using namespace std;
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> f; f[0]=1;
    int prefix=0,count=0;
    for(int n:nums){prefix+=n;count+=f.count(prefix-k)?f[prefix-k]:0;f[prefix]++;}
    return count;
}

C

#include <stdlib.h>
int subarraySum(int* nums, int n, int k) {
    /* Use hash map of prefix sums; for simplicity with small values use offset array */
    int count=0, prefix=0, freq[20001]={0}; freq[10000]=1;
    for(int i=0;i<n;i++){
        prefix+=nums[i];
        int need=prefix-k+10000;
        if(need>=0&&need<=20000) count+=freq[need];
        freq[prefix+10000]++;
    }
    return count;
}