560. Subarray Sum Equals K

560

MediumArrays and HashingHash map of prefix sumsPrefix-sum complement count

Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose elements sum to exactly k.

Open official problem prompt ↗

In plain English

Count how many contiguous slices of the array add up to exactly k, including slices that overlap.

Picture it like this

Think of running mileage markers on a road. A stretch of road covers exactly k miles whenever two markers differ by k, so at each marker you ask how many earlier markers sat exactly k miles behind you.

Example

Input: nums = [1, 1, 1], k = 2
Output: 2
Why: The subarrays nums[0..1] and nums[1..2] both sum to 2.

Constraints

1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7

Pattern lesson

See the pattern, then code

Prefix-sum complement count

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. A subarray (j, i] sums to k exactly when prefix[i] - prefix[j] = k. So for the running prefix P, every earlier prefix equal to P - k ends a qualifying subarray; count how many times each prefix value has occurred.

New words, made simpleKnow these before the algorithm

Prefix sum: The cumulative total of all elements from the start up to the current index.
Complement prefix: The earlier prefix value P - k that, subtracted from the current prefix P, leaves exactly k.
Frequency map: A dictionary counting how many times each prefix sum has appeared.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

All subarrays

Too slow for n up to 2*10^4 when done naively across all pairs.

Enumerate every start and end, summing each subarray.

Time O(n^2)Space O(1)

Sliding window

Invalid here: negative numbers break the monotonic growth a window relies on.

Grow and shrink a window to hit sum k.

Time O(n)Space O(1)

Best choicePrefix-sum hash map

Handles negatives and counts overlaps correctly in one pass.

Count occurrences of each prefix sum and look up prefix - k.

Time O(n)Space O(n)

The rule we keep true

Invariant

Before processing index i, seen maps each prefix value produced by nums[0..i-1] to its number of occurrences, and count equals the number of qualifying subarrays ending at or before i-1.

Why this is correct

Reasoning

A subarray ending at i sums to k iff its start j satisfies prefix[i] - prefix[j] = k, i.e. prefix[j] = prefix[i] - k. Each stored occurrence of that value marks one valid start, so adding its frequency counts every such subarray. Seeding {0:1} accounts for subarrays starting at index 0.

The algorithm in three movesSay these aloud before coding

1Keep a running prefix sum and a map from prefix value to how many times it has occurred, seeded with {0: 1}

seen={0:1}; prefix=1 -> need -1 (0 seen) count+=0; seen={0:1,1:1}

2At each element, add it to the prefix

prefix=2 -> need 0 (1 seen) count+=1; seen adds 2

3Add the count of prefix - k already seen to the answer

prefix=3 -> need 1 (1 seen) count+=1 -> total 2

4Record the current prefix in the map

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readprefix = 1

2 · AskHow many prefixes equal 1 - 2 = -1?

3 · Update stateseen = {0:1}

4 · Resultcount += 0; seen = {0:1, 1:1}

Key takeaway

When the running prefix hits 2 and 3, the required earlier prefixes 0 and 1 have each been seen once.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5Seed the map
{0: 1} represents the empty prefix so subarrays that begin at index 0 are counted.
2
Lines 6-8Update, count, record
Extend the prefix, add how many earlier prefixes equal prefix - k, then log the new prefix — order matters so a subarray of length 0 is never counted.
3
Lines 9Return the tally
count holds the total number of qualifying subarrays.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k = 0 with a zero-sum subarray, e.g. [1, -1]
Negative numbers producing repeated prefix values
Single-element array where nums[0] == k gives 1
Long runs where the same prefix recurs many times, each adding to the count

Common beginner mistakes

Forgetting to seed {0: 1}, which misses subarrays starting at index 0
Recording the current prefix before counting, which can count an empty subarray
Attempting a sliding window and getting wrong answers because negatives violate its assumptions

Check your understanding

Why must you add to count before inserting the current prefix into the map?

Subarray Sum Equals K

Subarray Sum Equals K

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing