Subarray Sum Equals K
Find number of subarrays with sum K.
Problem Understanding
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
Strategy (HashMap + Prefix Sum)
We want Sum(i, j) == k.
Since Sum(i, j) = Prefix[j] - Prefix[i-1], we want:Prefix[j] - Prefix[i-1] == k
=> Prefix[i-1] == Prefix[j] - k.
Algorithm:
Iterate through array, maintaining
current_sum.Check HashMap: how many times have we seen
current_sum - kbefore?Add that count to our answer.
Add
current_sumto the HashMap.
Interactive Visualization
Initializing...
Visualize how prefix sums accumulate. In this problem, we look back to find if (CurrentSum - k) occurred before.
Edge Cases
Watch out for:
Negative Numbers: Prefix sums are not monotonic! Cannot use Sliding Window (Two Pointers). Must use HashMap.
k = 0: Subarrays with sum 0 are valid.
Zeroes: Multiple zeroes increase count significantly.
Complexity Analysis
- Time Complexity: O(N). Single pass.
- Space Complexity: O(N). Hash map can store up to N distinct sums.
Dry Run
Nums: [1, 1, 1], k=2. Map: {0:1}. Count=0. sum=0.
| Num | New Sum | Check (Sum-k) | Map Has Check? | Action | Map Update |
|---|---|---|---|---|---|
| 1 | 1 | 1 - 2 = -1 | No | - | {0:1, 1:1} |
| 1 | 2 | 2 - 2 = 0 | Yes (val=1) | Count += 1 | {0:1, 1:1, 2:1} |
| 1 | 3 | 3 - 2 = 1 | Yes (val=1) | Count += 1 | {0:1, 1:1, 2:1, 3:1} |
Result: 2.
Solution
O(N) Time, O(N) Space.
1class Solution:2 def subarraySum(self, nums: List[int], k: int) -> int:3 count = 04 curr_sum = 05 prefix_map = {0: 1} # Base case: sum 0 occurs once67 for num in nums:8 curr_sum += num910 if (curr_sum - k) in prefix_map:11 count += prefix_map[curr_sum - k]1213 prefix_map[curr_sum] = prefix_map.get(curr_sum, 0) + 11415 return count