Learning Outcome
After this lesson, you should be able to convert subarray sum questions into prefix sum difference lookups.
Problem Statement
Given nums and k, return the number of continuous subarrays whose sum equals k.
| Input | Output | Why |
|---|---|---|
nums = [1,1,1], k = 2 | 2 | The subarrays at indexes 0..1 and 1..2 both sum to 2. |
Brute Force Approach
Check every start and end index and compute each subarray sum. This is quadratic.
Optimized Approach
Maintain a running prefix sum. If currentSum - k appeared before, each occurrence forms a valid subarray ending here.
Exact Pseudocode
freq[0] = 1
sum = 0
answer = 0
for x in nums:
sum += x
answer += freq[sum - k]
freq[sum] += 1
return answerReference Code
from collections import defaultdict
class Solution:
def subarraySum(self, nums, k):
freq = defaultdict(int)
freq[0] = 1
total = 0
answer = 0
for x in nums:
total += x
answer += freq[total - k]
freq[total] += 1
return answerSample Dry Run
| Step | State | Result |
|---|---|---|
| Start | freq[0] = 1 | Subarrays from index 0 are counted |
| First 1 | sum = 1, need -1 | answer = 0 |
| Second 1 | sum = 2, need 0 | answer = 1 |
| Third 1 | sum = 3, need 1 | answer = 2 |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n) | Each number updates the running sum and hash map once. |
| Space | O(n) | The map can store many distinct prefix sums. |
Edge Cases
- Negative numbers make sliding window unreliable.
- freq[0] is required for subarrays starting at index 0.
- Multiple equal prefix sums must be counted, not just stored as true or false.
Interview Checklist
- Use prefix sum difference currentSum - k.
- Add existing frequency before incrementing current sum frequency.
- Store counts, not just a set.
FAQs
Why does currentSum - k matter?
If an earlier prefix equals currentSum - k, the subarray after that prefix sums to k.
Why not use sliding window?
Sliding window fails when negative numbers can shrink or grow sums unpredictably.
What is the core pattern?
Prefix sum with hash map frequency.