LeetCode 560 Subarray Sum Equals K - Example and Complexity Analysis

Trace nums = [1, 2, 3] with k = 3.

Initialize: prefixSum = 0, count = 0, sumCount = {0: 1}.

i = 0: prefixSum = 1. Check 1 - 3 = -2. Not in map. Store {0: 1, 1: 1}.

i = 1: prefixSum = 3. Check 3 - 3 = 0. Found with count 1. count = 1. Store {0: 1, 1: 1, 3: 1}.

i = 2: prefixSum = 6. Check 6 - 3 = 3. Found with count 1. count = 2. Store {0: 1, 1: 1, 3: 1, 6: 1}.

The two subarrays summing to 3 are: [1, 2] and [3].

One pass through $n$ elements. $O(n)$ time. Hash map stores at most $n$ prefix sums. $O(n)$ space.