FAANG · LeetCode #560

Subarray Sum Equals K — three-stage drill

1The ProblemMedium

Subarray Sum Equals K

Count contiguous subarrays whose sum equals k (values may be negative).

Examples

[4,2,-2,4,2], k=4→ 5[1,2,3], k=10→ 0

constraintValues may be negative.

2The PatternTIME O(n) · SPACE O(n)

Prefix Sum

Running cumulative totals turn range-sum questions into O(1) lookups.

Problems using this pattern

3The SolutionRESULT → 5

Step through it

start: seen = {0: 1}, count = 0

Step 1 / 7

Python▎prefix + map lookup

1def subarraySum(nums, k):
2    count = 0
3    prefix = 0
4    seen = {0: 1}
5    for x in nums:
6        prefix += x
7        count += seen.get(prefix - k, 0)
8        seen[prefix] = seen.get(prefix, 0) + 1
9    return count

why it worksUnlike a sliding window, this handles negatives: it counts prefix sums in a map instead of shrinking a window. seen[p] is how many times prefix sum p has occurred, so count += seen[prefix−k] adds every earlier start that closes a subarray summing to k — which is why a prefix seen twice bumps the count by 2.

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Subarray Sum Equals K — three-stage drill