Subarray Sum Equals K

Given an integer array nums and an integer k, count how many subarrays have elements that add up to exactly k.

A subarray is a non-empty run of consecutive elements. Two subarrays count separately whenever they start or end at different positions, even if they contain the same values. The array may contain negative numbers and zeros.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 2 · 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

Pattern Path · Hashing & Counting · problem 11 of 169

Start simple

Fix every start index and extend the end while keeping a running sum, counting hits: O(n²) time, O(1) space.

The key idea

Let prefix be the running sum of the elements seen so far. A subarray ending at the current position sums to k exactly when it starts right after some earlier point where the running sum was prefix - k, because the subarray's sum is the difference of the two running sums.

So walk the array once, and before recording the current running sum, add to the answer the number of earlier positions whose running sum was prefix - k. A hash map from running sum to its number of occurrences answers that in O(1). The map starts as {0: 1} to represent the empty prefix before the first element, which is what lets subarrays that start at index 0 be counted.

Counting occurrences (not just presence) matters: with zeros or negatives the same running sum can repeat, and each earlier occurrence is a different start position. A sliding window cannot work here because, with negative values, extending a window does not reliably increase its sum.

Complexity

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

Python

from collections import defaultdict

class Solution:
    def subarraySum(self, nums, k):
        seen = defaultdict(int)  # running sum -> how many prefixes reached it
        seen[0] = 1  # the empty prefix
        prefix = 0
        count = 0
        for x in nums:
            prefix += x
            count += seen[prefix - k]  # subarrays ending here that sum to k
            seen[prefix] += 1
        return count

JavaScript

var subarraySum = function(nums, k) {
  const seen = new Map([[0, 1]]); // running sum -> how many prefixes reached it
  let prefix = 0, count = 0;
  for (const x of nums) {
    prefix += x;
    count += seen.get(prefix - k) || 0; // subarrays ending here that sum to k
    seen.set(prefix, (seen.get(prefix) || 0) + 1);
  }
  return count;
};

What the interviewer is checking

It tests the prefix-sum-plus-hash-map pattern and whether you can explain why the usual two-pointer window breaks with negative numbers.

Mistakes to avoid

• Forgetting to seed the map with {0: 1}, which misses subarrays starting at index 0.
• Storing a set of prefix sums instead of counts, undercounting when sums repeat.
• Updating the map before querying it, which counts the empty subarray when k = 0.
• Using a sliding window, which is only valid when all numbers are positive.

Follow-ups to expect

• Return the longest such subarray. (Store first index per prefix sum.)
• Count subarrays whose sum is divisible by k. (Prefix sums modulo k.)
• What if all numbers are positive? (Sliding window, O(1) space.)

In real software

Analytics systems count time ranges whose net change (deposits minus withdrawals, or traffic in minus out) equals a target using running totals indexed in a hash map.

Practice next