Subarray Sum Equals K — Prefix Sum + Hashmap

What does it solve?

Given an array and a target k, count how many contiguous subarrays sum exactly to k — including negative numbers, in a single pass.

The sum of any subarray [j+1..i] equals prefixSum[i] - prefixSum[j]. So a subarray summing to k exists ending at i whenever some earlier prefix sum equals prefixSum[i] - k.

The core idea

// map: prefixSum value → how many times seen
map = {0: 1} // empty prefix
prefixSum = 0
for each x in nums:
  prefixSum += x
  count += map[prefixSum - k] // if present
  map[prefixSum]++

Complexity

Time complexity

O(n)

One pass — every element does a constant-time hashmap lookup and update.

Space complexity

O(n)

Up to n+1 distinct prefix sums can be stored in the hashmap.

Examples & edge cases

Live animation

🎯 Target k: —

current index looking up in map found — counts added not found

Array

prefix sum

need = sum − k

—

Hashmap (prefix sum → frequency)

Step — of —

Prefix sum

—

Looking for

—

Count

—

subarrays found

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	i	prefixSum	need	Found?	Count

C++ implementation

subarray_sum_equals_k.cpp

#include <bits/stdc++.h>
using namespace std;

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    freq[0] = 1;              // empty prefix sums to 0

    int prefixSum = 0, count = 0;
    for (int x : nums) {
        prefixSum += x;
        int need = prefixSum - k;
        if (freq.count(need)) count += freq[need];
        freq[prefixSum]++;
    }
    return count;
}

int main() {
    vector<int> nums = {1,1,1};
    int k = 2;
    cout << "Count: " << subarraySum(nums, k) << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars