Subarray Sum Equals K

medium prefix sum hash map

Problem

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Inputnums = [1, 1, 1], k = 2

Output2

If running prefix is P, count occurrences of P − k seen so far.

nums (comma-separated)

def subarray_sum(nums, k):
    counts = {0: 1}
    prefix = 0
    answer = 0
    for x in nums:
        prefix += x
        answer += counts.get(prefix - k, 0)
        counts[prefix] = counts.get(prefix, 0) + 1
    return answer

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

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

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> counts;
    counts[0] = 1;
    int prefix = 0, answer = 0;
    for (int x : nums) {
        prefix += x;
        if (counts.count(prefix - k)) answer += counts[prefix - k];
        counts[prefix]++;
    }
    return answer;
}

Explanation

We want to count subarrays that sum to k. Checking every start/end pair is slow, so we use a running prefix sum together with a hash map that remembers how often each prefix total has appeared.

The key fact: a subarray ending at the current spot sums to k exactly when some earlier prefix equals prefix - k. If we have seen that earlier prefix several times, each occurrence marks a different valid starting point, so we add all of them.

As we sweep, at each number we update prefix += x, then do answer += counts[prefix - k], and finally record the current prefix with counts[prefix] += 1. We seed the map with {0: 1} so subarrays that start at index 0 are counted.

Example: nums = [1,1,1], k = 2. Prefixes go 1, 2, 3. At prefix 2 we look for 0 (seen once) → one match; at prefix 3 we look for 1 (seen once) → another. Total 2.

Each lookup and insert is constant time, so the whole count is O(n) time and O(n) space for the map.

Time: O(n) Space: O(n)