9. Subarray Sum Equals K · DSA Practice

Count the contiguous subarrays of nums whose elements add up to exactly k. Values can be negative.

Example 1

Input: nums = [1,2,3,-2,2], k = 3

Output: 4

Explanation: [1,2], [3], [2,3,-2] and [3,-2,2] all sum to 3.

Example 2

Input: nums = [1,-1,0], k = 0

Output: 3

Constraints

1 ≤ nums.length ≤ 2·10⁴
-1000 ≤ nums[i] ≤ 1000

Hint 1

sum(i..j) = prefix[j] − prefix[i−1].

Hint 2

So for each prefix, count how many earlier prefixes equal prefix − k.

Hint 3

Sliding window does NOT work here because values can be negative.

Prefix SumHash Table

Approach 1: All subarrays

Two loops with a running sum.

⏱ Time O(n²)💾 Space O(1)

Approach 2: Prefix sums + hash map ✅

Keep a count of every prefix sum seen; each new prefix adds seen[prefix − k] to the answer.

⏱ Time O(n)💾 Space O(n)

Reference solution for Prefix sums + hash map (time O(n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        seen = defaultdict(int)
        seen[0] = 1                  # empty prefix
        prefix = count = 0
        for x in nums:
            prefix += x
            count += seen[prefix - k]   # earlier prefixes that leave exactly k
            seen[prefix] += 1
        return count

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> seen{{0, 1}};  // empty prefix
        int prefix = 0, count = 0;
        for (int x : nums) {
            prefix += x;
            auto it = seen.find(prefix - k);
            if (it != seen.end()) count += it->second;
            seen[prefix]++;
        }
        return count;
    }
};

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Arrays, Hashing & Prefix Sums.