Subarray Sum Equals K — Prefix Sum + Hash Map

What does it solve?

Count how many contiguous subarrays sum to exactly k. Because values can be negative, a sliding window won't work, so we lean on prefix sums instead.

Key insight: a subarray (j, i] sums to k exactly when prefix[i] − prefix[j] = k, i.e. prefix[j] = prefix[i] − k. Keep a hash map of prefix-sum → how many times it occurred. At each i, add the count of prefix − k. Seed the map with {0: 1} so subarrays starting at index 0 are counted. One pass → O(N).

The core idea

// count[prefixSum] = occurrences
count = {0: 1}; pre = 0; ans = 0
for x in nums:
  pre += x
  ans += count.get(pre − k, 0)
  count[pre] += 1

Complexity

Time complexity

O(N)

Single pass. Each element does one O(1) map lookup and one O(1) insert. No nested subarray scan.

Space complexity

O(N)

In the worst case every prefix sum is distinct and stored in the map.

Examples & edge cases

Live animation — running prefix sum, look up prefix − k in the map

current element prefix stored probing prefix−k subarray(s) found

nums · k = — (number under each cell = running prefix)

Press Play to begin…

Hash map — prefix sum → count

{ 0: 1 } seeded

Current step detail

i = — prefix = — need = — count = —

Step — of —

nums[i]

—

current value

prefix sum

—

sum up to i

looking for

—

prefix − k

subarrays

—

total found

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	i	nums[i]	prefix	need = pre−k	in map?	+found	count

C++ implementation

subarray_sum_k.cpp

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

// Count contiguous subarrays summing to k (works with negatives)
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> count;
    count[0] = 1;               // empty prefix: enables subarrays from index 0

    int pre = 0, ans = 0;
    for (int x : nums) {
        pre += x;                  // running prefix sum
        // subarrays ending here that sum to k = times we saw pre-k before
        if (count.count(pre - k)) ans += count[pre - k];
        count[pre]++;              // record this prefix sum
    }
    return ans;
}

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

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars