Topic · Prefix SumMedium
Subarray Sum Equals K
Understand the problem
Given an integer array nums (which may contain negative numbers) and an integer k, count the contiguous subarrays whose sum equals k.
Example:
ts
nums = [1, 2, 3], k = 3
output = 2 // two subarrays: [1, 2] and [3]
nums = [1, -1, 0], k = 0
output = 3 // [1, -1], [0], [1, -1, 0]Note right away: because the array has negative numbers, the window sum is not monotonic as the window grows — Sliding Window resizes the window on the assumption that "the sum increases when you add an element", so it doesn't apply.
That is the signal to switch to prefix sum + hash map.
Basic approach
O(n²) time, O(1) spacets
function subarraySum(nums: number[], k: number): number {
let count = 0
// try every subarray [i..j]
for (let i = 0; i < nums.length; i++) {
let sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j]
if (sum === k) count++
}
}
return count
}Why this approach is slow:
Consider every start i and end j — accumulating along j makes each subarray O(1), but there are n(n+1)/2 subarrays.
With n = 2·10⁴ that is about 2·10⁸ steps, too slow.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.