MediumNeetCode150ArrayHash TablePrefix Sum
Subarray Sum Equals K
Count subarrays summing to k.
Examples
Input
nums = [1,1,1], k = 2
Output
2
[1,1] at positions (0,1) and (1,2).
Constraints
- •
1 <= nums.length <= 2*10^4 - •
-1000 <= nums[i] <= 1000 - •
-10^7 <= k <= 10^7
Approaches
Check all subarrays.
CodeT: O(n^2) | S: O(1)
Count prefix sums.
CodeT: O(n) | S: O(n) hash map
def subarraySum(nums, k):
m={0:1}; s=0; cnt=0
for n in nums:
s+=n
if s-k in m: cnt+=m[s-k]
m[s]=m.get(s,0)+1
return cntSame approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check all subarrays. |
| Prefix Sum + HashMap | O(n) | O(n) hash map | Count prefix sums. |
| Prefix Sum Optimized | O(n) | O(n) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Check all subarrays.
Prefix Sum + HashMap
T: O(n)S: O(n) hash map
Count prefix sums.
Prefix Sum Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling negative numbers
Wrong prefix sum calc
Off-by-one