Count Subarrays Summing to K

Medium20–25 min

Topics

ArrayPrefix SumHash Table

Companies

AmazonMicrosoftGoogleFacebook

Given an array of integers nums (which may include negative values) and an integer k, return the total number of contiguous subarrays whose elements sum to exactly k. Overlapping subarrays all count separately. Checking every subarray directly works, but it re-derives sums that share almost all of their elements with a sum already computed. A prefix sum turns "does some subarray ending here sum to k" into "has an earlier prefix sum equal to (current prefix sum − k)" — a question a hashmap of prefix-sum frequencies can answer in O(1), letting the whole array be processed in a single pass.

Test Case 1:

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

Output:2

Explanation:Both [1, 1] at indices 0-1 and [1, 1] at indices 1-2 sum to 2.

Test Case 2:

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

Output:2

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

Test Case 3:

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

Output:3

Explanation:[1, -1], [0], and [1, -1, 0] all sum to 0 — negatives make several subarrays valid.

Constraints

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

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-10 integers, -10 to 10k (target sum)

1	class Solution {
2	public int countSubarraysSummingToK(int[] nums, int k) {
3	Map<Integer, Integer> freq = new HashMap<>();
4	freq.put(0, 1);
5	int sum = 0, count = 0;
6	for (int num : nums) {
7	sum += num;
8	count += freq.getOrDefault(sum - k, 0);
9	freq.put(sum, freq.getOrDefault(sum, 0) + 1);
10	}
11	return count;
12	}
13	}
14

Array

HashMap

0→1

Variables

sum0

count0

INITIALIZE

Seed the frequency map with {0: 1} — the empty prefix (sum 0) has occurred once before we've read anything. Start sum at 0 and count at 0.

Step 1 / 11

Approach & Solutions

Brute Force

Brute

Try every subarray directly: for each start index, extend the end index forward while accumulating a running sum, and count it every time that sum equals k. Correct for any mix of positive, negative, or zero values, but it re-sums overlapping ranges from scratch instead of reusing work already done.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int countSubarraysSummingToK(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;
    }
}

Optimal — Prefix Sum + Hash Map

Optimal

Track a running prefix sum while walking the array once, and keep a hashmap of how many times each prefix-sum value has occurred so far (seeded with {0: 1} for the empty prefix before any elements). At each index, if an earlier prefix sum equals the current sum minus k, every one of those earlier occurrences marks the start of a subarray ending here that sums to exactly k — so add its frequency straight into the running count, then record the current prefix sum for future indices to look back on.

TimeO(n)

SpaceO(n)