Subarray Sum Equals K

Medium#560subarray sum

You get an array of integers, negative ones included, and a number k. Count the contiguous subarrays whose numbers add up to exactly k. Our example: [1, 2, -1, 3, -2, 2] and k = 3 — the answer is 4: [1, 2], [3], [3, -2, 2] and [1, 2, -1, 3, -2].

560 Subarray Sum Equals KWalkthrough · 1×

Example: [1, 2, -1, 3, -2, 2], k = 3. Under the numbers are the running sums: prefix j stands before nums[j]; a bracket marks a subarray found.

numsprefix12-13-22
not reached yetalready seencurrentearlier prefix equal to needsubarray with sum k

No subarrays found yet: count = 0

01/38
restart · back · play · step
Speed
1function subarraySum(nums, k):
2 count = 0
3 prefix = 0
4 seen = map {0: 1} // missing keys: 0
5 for each x in nums:
6 prefix = prefix + x
7 need = prefix - k
8 if need in seen:
9 count = count + seen[need]
10 seen[prefix] = seen[prefix] + 1
11 return count
state
count
0
prefix
–
seen
–
x
–
need
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The sum of a subarray is the running sum at its end minus the running sum before its start. So a subarray ending here adds up to k exactly when an earlier prefix equals prefix − k, and seen says how many such prefixes there were.
  2. seen starts with {0: 1}, the empty prefix before index 0. Without it, [1, 2] and [1, 2, -1, 3, -2], which start at index 0, would never be counted.
  3. Negative numbers break a sliding window: the sum drops and grows again, as in [1, 2, -1, 3, -2]. A difference of prefixes does not care about signs.

Complexity

Time O(n): one pass, and a map lookup or update takes O(1) on average. Memory O(n): seen may hold n + 1 different prefixes.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.