Subarray Sum Equals K

Medium Problem 13 of 151 Java and Python

Problem

Given an integer array nums and an integer k, return the number of contiguous, non-empty subarrays whose elements add up to exactly k.

Example 1

Input: nums = [1, 1, 1], k = 2
Output: 2
Why: The subarrays [1, 1] at positions 0–1 and 1–2.

Example 2

Input: nums = [1, 2, 3], k = 3
Output: 2
Why: [1, 2] and [3].

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷

Explanation

Let prefix be the running sum up to the current index. A subarray that ends here and sums to k exists for every earlier point where the running sum was prefix - k.

So keep a map of how many times each running sum has occurred, and at each step add count[prefix - k] to the answer. Negative numbers are why a sliding window does not work here.

Approach 1 · Naive

Every start, running sum

Time O(n²)
Space O(1)

For every start index, extend the subarray and count each time the sum equals k.

For each i, set sum = 0.
For each j ≥ i, add nums[j]; if sum == k, increment the count.

Java

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        for i in range(len(nums)):
            total = 0
            for j in range(i, len(nums)):
                total += nums[j]
                if total == k:
                    count += 1
        return count

Approach 2 · Optimal

Prefix sums with a hash map

Time O(n)
Space O(n)

Count how often each running sum has appeared. Every earlier running sum equal to prefix - k marks the start of a subarray that sums to k.

Start with seen = {0: 1} (the empty prefix) and prefix = 0.
For each number, add it to prefix.
Add seen[prefix - k] (or 0) to the answer.
Increment seen[prefix].

Java

import java.util.*;

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

Python

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        seen = defaultdict(int)
        seen[0] = 1
        prefix = count = 0
        for num in nums:
            prefix += num
            count += seen[prefix - k]
            seen[prefix] += 1
        return count

Complexity compared

Approach	Time	Space
Naive Every start, running sum	O(n²)	O(1)
Optimal Prefix sums with a hash map	O(n)	O(n)

Key takeaways

sum(i..j) = prefix[j] – prefix[i – 1]: most "subarray with sum X" problems reduce to this.
Seed the map with {0: 1} so subarrays starting at index 0 are counted.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem