Subarray Sum Equals K

Problem

LeetCode 560 — Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k.

Example

nums = [1, 1, 1], k = 2  →  2
nums = [1, 2, 3], k = 3  →  2   (subarrays: [1,2] and [3])

Approaches

Approach 1 — Brute Force: O(n^3)

For each subarray size s from n down to 1, and for each starting position, compute the sum from scratch and check if it equals k. Three nested loops → O(n^3).

Approach 2 — Maintained Sum Array: O(n^2)

Keep an array maintain where maintain[i] = sum of the subarray of the current size starting at index i. For each size s from 1 to n, extend each entry by one element: maintain[i] += nums[i + s - 1]. Check maintain[i] == k for all valid i. Avoids recomputing sums from scratch — each step is O(n), total O(n^2).

Approach 3 — Prefix Sum + HashMap: O(n)

Key insight: if prefixSum[j] - prefixSum[i] == k, then the subarray (i, j] sums to k. Rearranged: we need prefixSum[i] == prefixSum[j] - k.

Walk left-to-right maintaining a running prefix sum. At each index j, the number of valid subarrays ending at j is the count of earlier indices where the prefix sum equalled running - k. Store those counts in a Map<prefixSum, frequency>.

Seed the map with {0: 1} to handle subarrays that start from index 0 (i.e., prefix sum itself equals k).

Why two-pointer doesn’t work: values can be negative, so the subarray sum is not monotone as the window expands — you can’t decide to shrink based on sum alone.

Solution

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int prefixSum = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            prefixSum = prefixSum + nums[i];
            int totalSubarray = map.getOrDefault(prefixSum - k, 0);
            result = result + totalSubarray;
            map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
        }
        return result;
    }
}

Walkthrough on [1, 2, 3], k = 3

Answer: 2. Subarrays found: [1,2] (indices 0–1) and [3] (index 2).

Complexity

• Time: O(n)
• Space: O(n) for the map

Why It Teaches You Something

“Range sum equals X” → look up the complement in a map. The same pattern unlocks:

• Subarray Sum Divisible by K (LC 974) — store prefixSum % k in the map
• Continuous Subarray Sum (LC 523) — same modulo trick, check for gap ≥ 2
• Count of Range Sum (LC 327) — harder variant, needs a sorted structure
• Path Sum III (LC 437) — same idea on a tree with DFS prefix sums