Complement / Two Sum

Subarray Sum = K

Maintain a running prefix sum. At each position, check if (prefixSum − K) exists in the map — if it does, there's a subarray between that earlier position and now that sums to K. Store each prefix sum in the map.

O(n)

How It Works

Counting subarrays that sum to K combines prefix sums with a hash map. The sum of a subarray (i, j] equals prefix[j] − prefix[i], so a subarray summing to K ends at j exactly when some earlier prefix equals prefix[j] − K. Scan once, maintaining the running sum and a map from each prefix-sum value to how many times it has occurred; at each element, add the count of (runningSum − K) to the answer, then record the running sum.

Seeding the map with {0: 1} handles subarrays that start at index zero. One pass gives O(n) time and space, and because the map counts occurrences rather than positions, it correctly handles negative numbers — where sliding window techniques break down.

Step-by-Step Visualization

Count subarrays summing to K=3

Prefix0

Count0

Map

0 1

1/4

Code

Java

static int subarraySum(int[] nums, int k) {
  Map<Integer, Integer> map = new HashMap<>();
  map.put(0, 1);
  int prefix = 0, count = 0;

  for (int num : nums) {
    prefix += num;
    count += map.getOrDefault(prefix - k, 0);
    map.put(prefix, map.getOrDefault(prefix, 0) + 1);
  }
  return count;
}

Tips & Gotchas

1Use prefix sum + hash map to find subarrays summing to K

2Key insight: if prefix[j] - prefix[i] = K, subarray [i+1..j] sums to K

3Initialize map with {0: 1} for subarrays starting at index 0

Practice Problems

1Subarray Sum Equals K
2Continuous Subarray Sum
3Subarray Sums Divisible by K
4Binary Subarrays With Sum
5Contiguous Array

About the Complement / Two Sum Pattern

Instead of checking every pair, store each number in a map as you go. For each new number, check if the 'complement' (what you need to reach the target) is already in the map. One pass, O(n).

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

Why does a sliding window fail here but prefix sums work?

Sliding windows rely on the sum growing as the window expands, which breaks when negative numbers exist. Prefix sums make no monotonicity assumption: they simply record every partial sum seen, so any mix of positive and negative values is handled.

What is the purpose of putting 0 → 1 in the map before starting?

It represents the empty prefix before the array begins. Without it, a subarray that starts at index 0 and sums exactly to K would find no matching earlier prefix and be missed.

Should the map store counts or indices?

Store counts when counting subarrays, since several earlier prefixes may have the same value and each contributes a distinct subarray. Store the earliest index instead when the goal is the longest subarray with a given sum, as in Contiguous Array.