Subarray Sum Equals K
Problem
Return the number of contiguous subarrays whose sum equals k. The array can contain negative numbers.
Example 1
Input: nums = [1, 1, 1], k = 2 Output: 2
Example 2
Input: nums = [1, 2, 3], k = 3 Output: 2
[1, 2] and [3].
Test cases
Case 1
Input: [1,1,1], 2 Expected: 2
Case 2
Input: [1,2,3], 3 Expected: 2
Case 3
Input: [1,-1,0], 0 Expected: 3
View solutionHide solution2 approaches
1. All start points
Time O(n²)Space O(1)
Fix a start, extend the end while keeping a running sum.
function subarraySum(nums, k) { let res = 0; for (let i = 0; i < nums.length; i++) { let sum = 0; for (let j = i; j < nums.length; j++) if ((sum += nums[j]) === k) res++; } return res;}2. Prefix sum counts in a map
Time O(n)Space O(n)
A subarray ending here sums to k when some earlier prefix equals sum − k. Count how many earlier prefixes had each value.
function subarraySum(nums, k) { const count = new Map([[0, 1]]); let sum = 0, res = 0; for (const x of nums) { sum += x; res += count.get(sum - k) ?? 0; count.set(sum, (count.get(sum) ?? 0) + 1); } return res;}Sliding window fails here because numbers can be negative — interviewers often ask why.