Mediumprefix-sum
Subarray Sum Equals K
Problem (restated)
Given an array of integers and an integer k, return the total number of continuous subarrays whose sum equals k.
Intuition
Prefix sums: count how often (pref - k) has occurred. Each such earlier prefix forms a valid subarray ending here.
Approaches
Prefix sum + hash map
Tested onlyTime O(n)Space O(n)
Idea. count[0]=1. Walk array updating pref; ans += count[pref-k]; count[pref]++.
Walkthrough. nums=[1,1,1], k=2 → subarrays [1,1] twice → answer 2.
Trade-offs. Handles negatives (sliding window does not). Must seed count[0]=1.
Solution
export function subarraySum(nums: number[], k: number): number {
const count = new Map<number, number>([[0, 1]]);
let pref = 0, ans = 0;
for (const x of nums) {
pref += x;
ans += count.get(pref - k) ?? 0;
count.set(pref, (count.get(pref) ?? 0) + 1);
}
return ans;
}
export function subarraySum(nums: number[], k: number): number {
const count = new Map<number, number>([[0, 1]]);
let pref = 0, ans = 0;
for (const x of nums) {
pref += x;
ans += count.get(pref - k) ?? 0;
count.set(pref, (count.get(pref) ?? 0) + 1);
}
return ans;
}
Template connection
Prefix sum + hashmap from the Prefix Sum template.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?