Subarray Sum Equals K

Problem

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose elements sum to exactly k. The array may contain negatives, so a sliding window does not work — count prefix sums with a hash map instead.

Constraints

• 1 ≤ nums.length ≤ 2·10⁴
• −1000 ≤ nums[i] ≤ 1000
• −10⁷ ≤ k ≤ 10⁷

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def subarraySum(self, nums, k):
        from collections import defaultdict
        seen = defaultdict(int)
        seen[0] = 1
        s = cnt = 0
        for x in nums:
            s += x
            cnt += seen[s - k]
            seen[s] += 1
        return cnt

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.