Subarray Sum Equals K

Approach Summary

Track prefix sums in a hash map. At each position, if (currentSum - k) exists in the map, that count is the valid subarrays ending here.

Full Solution & Approach

The sum of any subarray [j, i] equals prefix[i] - prefix[j-1], so asking for subarrays summing to k is asking for pairs of prefix sums that differ by k. Maintain a running prefix sum and a hash map counting how many times each prefix value has occurred. At each index, the number of subarrays ending here that sum to k equals the count of (running - k) already seen in the map — because every previous prefix that equals running - k forms exactly one valid subarray ending here. Then record the current running prefix in the map and continue. Initialize the map with {0: 1} so a subarray starting at index 0 is counted. This converts a brute-force O(n²) pair scan into a single pass — the canonical prefix-sum-plus-hash-map pattern that also solves longest-equal-sum and contiguous-array problems.

One pass with O(1) map operations per element — O(n) time. The map holds up to n distinct prefix sums — O(n) space.

Solution Code

Solution

def subarray_sum(nums: list[int], k: int) -> int:
    counts = {0: 1}
    running = 0
    total = 0
    for n in nums:
        running += n
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total

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

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);
    int running = 0, total = 0;
    for (int n : nums) {
        running += n;
        total += counts.getOrDefault(running - k, 0);
        counts.merge(running, 1, Integer::sum);
    }
    return total;
}

int subarraySum(const vector<int>& nums, int k) {
    unordered_map<int,int> counts;
    counts[0] = 1;
    int running = 0, total = 0;
    for (int n : nums) {
        running += n;
        total += counts[running - k];
        counts[running]++;
    }
    return total;
}

Edge Cases to Watch

Negative numbers — prefix sums are not monotonic, but the hash map handles any values
k = 0 — counts subarrays summing to zero, including empty-ish runs
A single element equal to k
The whole array summing to k — handled by the {0: 1} initialization

How to Recognize This Pattern

Count subarrays with exact sum
Prefix sum + hash map

Complexity Analysis

Time Complexity

O(n)

Space Complexity