Subarray Sum Equals K (LC 560)

Pattern: Hashing - Prefix Sum + HashMap
Difficulty: Medium
Key Concept: Store prefix sum frequencies to find subarrays with target sum in O(n)

1. Problem Statement

Given an integer array nums and an integer k, return the number of contiguous subarrays whose elements sum to exactly k.

A subarray is a contiguous non-empty sequence of elements from the array.

Constraints (typical):

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

---

2. Algorithm (Prefix Sum + HashMap)

Idea: If prefixSum[j] is the sum of nums[0..j] and prefixSum[i-1] is the sum of nums[0..i-1], then the sum of subarray nums[i..j] is prefixSum[j] - prefixSum[i-1]. We want that to equal k, so prefixSum[i-1] = prefixSum[j] - k. For each index j, count how many earlier prefix sums equal prefixSum[j] - k.

Pseudocode:

count = 0
prefixSum = 0
map = empty map from int -> int   // frequency of each prefix sum seen so far

map[0] = 1   // empty prefix before index 0

for each x in nums:
    prefixSum += x
    // subarrays ending here with sum k: need (prefixSum - k) seen before
    count += map.getOrDefault(prefixSum - k, 0)
    map[prefixSum] = map.getOrDefault(prefixSum, 0) + 1

return count

---

3. Beginner Analysis — Why Prefix Sums Work

• A prefix sum at position j is the sum of all elements from the start through j.
• Any subarray ending at j can be written as: (sum from start to j) minus (sum from start to just before the subarray starts).
• So if the subarray sum must be k, we need: currentPrefix - olderPrefix = k, i.e. olderPrefix = currentPrefix - k.
• We do not store every subarray**; we only store how many times each prefix sum has appeared. That is enough because any earlier occurrence of prefixSum - k pairs with the current prefix to form one valid subarray ending here.
• map.put(0, 1) accounts for subarrays that start at index 0: when currentPrefix == k, we need one “virtual” prefix of sum 0 before the array.

---

4. Dry Run — nums = [1, 1, 1], k = 2

Step	x	prefixSum	Look up prefixSum - k	Add to count	map after update
init	—	0	—	0	{0: 1}
i=0	1	1	1-2 = -1 → 0	0	{0:1, 1:1}
i=1	1	2	2-2 = 0 → 1	1	{0:1, 1:1, 2:1}
i=2	1	3	3-2 = 1 → 1	2	{0:1, 1:1, 2:1, 3:1}

Subarrays with sum 2: [1,1] at indices 0–1, and [1,1] at indices 1–2 → count = 2.

---

5. Brute Force Java — O(n²)

Nested loops: for each start, extend end and track running sum.

class SolutionBrute {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

---

6. Optimal Java — Prefix Sum + HashMap

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int prefixSum = 0;
        Map<Integer, Integer> freq = new HashMap<>();
        freq.put(0, 1);

        for (int x : nums) {
            prefixSum += x;
            count += freq.getOrDefault(prefixSum - k, 0);
            freq.put(prefixSum, freq.getOrDefault(prefixSum, 0) + 1);
        }
        return count;
    }
}

Alternative increment using merge:

for (int x : nums) {
    prefixSum += x;
    count += freq.getOrDefault(prefixSum - k, 0);
    freq.merge(prefixSum, 1, Integer::sum);
}

---

7. Java & Language Tricks

Topic	Note
Map.getOrDefault(prefixSum - k, 0)	Avoids null when key missing; treats missing as frequency 0.
map.merge(key, 1, Integer::sum)	Upsert: add 1 to existing count or insert 1.
C++ unordered_map	map[x]++ default-constructs missing keys to 0 (similar ergonomics).
Python defaultdict(int)	Missing keys behave as 0 without explicit get.
freq.put(0, 1)	Required for subarrays starting at index 0 when prefixSum == k.

---

8. Complexity

Approach	Time	Space
Brute force (nested loops)	O(n²)	O(1)
Prefix sum + HashMap	O(n)	O(n)

The HashMap holds at most O(n) distinct prefix sums in the worst case.