Subarray Sum Equals K

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.