270. Subarray Sum Equals K

Try every possible subarray by fixing a start index and extending the end index, accumulating the running sum.

Brute Force

For each starting index i, compute the running sum as we extend j from i to n-1. Whenever the running sum equals k, increment the count.

Two nested loops give O(n^2) time. Space is O(1) since we only track the running sum.

Why it is slow: Every pair (i, j) is examined, leading to quadratic time on large arrays.

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int total = 0;
            for (int j = i; j < nums.length; j++) {
                total += nums[j];
                if (total == k) {
                    count++;
                }
            }
        }
        return count;
    }
}

If prefix_sum[j] - prefix_sum[i] = k, then the subarray from i+1 to j sums to k. A hash map counting previous prefix sums lets us find all such i in O(1).

Mental Model

The prefix sum at index j is the sum of all elements from index 0 through j. If we know a prefix sum at some earlier index i equals prefix[j] - k, then the subarray between i+1 and j sums to exactly k. A hash map stores how many times each prefix sum has appeared so far, letting us count all valid starting points instantly.

Algorithm Steps

1. Initialize prefix = 0, count = 0, and a hash map freq = {0: 1} (an empty prefix sum of 0 exists once before we start).
2. For each element nums[j]:
   • Add nums[j] to prefix.
   • Look up prefix - k in freq. If it exists, add its count to count.
   • Increment freq[prefix] by 1.
3. Return count.

Worked Walk-through

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

Answer: 2 (subarrays [1,2] and [3])

Edge Cases

• k = 0 with zeros in array: Multiple overlapping subarrays of zeros all sum to 0.
• Negative numbers: prefix sums can decrease, so the same prefix sum can appear multiple times.
• Single element equal to k: prefix becomes k, and freq has {0:1}, so prefix-k=0 is found.

Complexity

• Time: O(n) — one pass through the array with O(1) hash map operations.
• Space: O(n) — the hash map stores at most n+1 distinct prefix sums.