Subarray Sum Equals K — Solution

Problem

Given an array of integers and a target value k, count how many contiguous subarrays have elements that add up to exactly k. The array can contain negative numbers, so a shrinking window won't always work.

• Input: nums = [1, 1, 1], k = 2
• Output: 2
• Explanation: Two subarrays sum to 2 — [1, 1] at indices 0–1 and [1, 1] at indices 1–2.

Counter-example: nums = [1, 2, 3], k = 3 → 2. Both [3] and [1, 2] qualify, even though they are different lengths.

Intuition

The brute-force scan works but does redundant work re-summing overlapping regions. The key insight is that any subarray from index i to j can be expressed as the difference of two prefix sums: prefix[j+1] - prefix[i]. So the question becomes: for each position, how many earlier prefix sums are exactly current_prefix - k? A hash map that stores how many times each prefix sum has appeared answers that in O(1) per position.

Approach 1 — Brute Force

For each starting index, sweep right while accumulating a running sum, and count every time it hits k.

1. Iterate over every possible start index left.
2. Reset a running sum to 0 at each new start.
3. Extend right from left to the end, adding each element to the running sum.
4. Whenever the running sum equals k, increment the count.
5. Return the total count.

1def subarraySum(nums: list[int], k: int) -> int:
2    count = 0
3    for left in range(len(nums)):
4        running_sum = 0
5        for right in range(left, len(nums)):
6            running_sum += nums[right]
7            if running_sum == k:
8                count += 1
9    return count

Time: O(n²) — every pair of (start, end) indices is visited once.
Space: O(1) extra — only two scalar variables beyond the input.

Approach 2 — Prefix Sum with Hash Map

Use cumulative prefix sums and a frequency map to turn each lookup from O(n) to O(1).

1. Seed the map with {0: 1} — this represents the empty prefix that exists before index 0, allowing subarrays starting at the beginning to be counted.
2. Walk through the array, maintaining a running cumulative sum.
3. At each position, compute current_sum - k; whatever value that is, look it up in the map — its count tells you how many subarrays ending here sum to exactly k.
4. Add that count to the answer, then record current_sum in the map.
5. Return the accumulated count.

1from collections import defaultdict
2
3def subarraySum(nums: list[int], k: int) -> int:
4    prefix_counts = defaultdict(int)
5    prefix_counts[0] = 1   # empty prefix before the array starts
6    current_sum = 0
7    count = 0
8
9    for num in nums:
10        current_sum += num
11        # every previous prefix equal to (current_sum - k) gives a valid subarray
12        count += prefix_counts[current_sum - k]
13        prefix_counts[current_sum] += 1
14
15    return count

Time: O(n) — one pass through the array with O(1) hash map operations.
Space: O(n) — the map holds at most one entry per distinct prefix sum.

Complexity Summary

Common Mistakes

• Forgetting to seed the map with {0: 1}: Without this, subarrays that start at index 0 are never counted, because there is no earlier index with a recorded prefix sum of 0.
• Using a sliding window instead of prefix sums: A two-pointer window can only shrink when the sum exceeds k, which only works for non-negative integers — negative values in the array make this approach incorrect.
• Recording current_sum before the lookup: If you add current_sum to the map first and then check current_sum - k, a subarray of length zero (starting and ending at the same index) will be counted whenever nums[i] == k, inflating the result.
• Checking current_sum == k as a special case: This is already handled by the {0: 1} seed — no special-casing needed; trust the general formula.
• Assuming prefix sums are unique: The map must store counts, not just presence, because the same prefix sum can appear at multiple positions (especially with zeros or alternating positives and negatives in the input).

Related Problems

• two-sum — same hash map complement pattern: store what you've seen, look up what you need
• contiguous-array — prefix sum with a hash map, finding the longest balanced subarray of 0s and 1s
• longest-consecutive-sequence — hash set for O(1) membership queries to avoid nested loops
• maximum-subarray — Kadane's algorithm, a different O(n) approach to subarray-sum problems
• find-all-anagrams-in-a-string — sliding window for fixed-length subarrays, contrasting technique when the window is bounded