How do you approach Subarray Sum Equals K?

Brute force checks all O(n^2) subarrays - think about prefix sums instead.

What is the time complexity of Subarray Sum Equals K?

Time complexity: O(n) - single pass. Space complexity: O(n) - the prefix-sum map.

What are common mistakes on Subarray Sum Equals K?

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0. Counting the current prefix before checking for its complement, so a zero-sum range matches itself. Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

gitGood.dev

← Back to problems

Subarray Sum Equals K

MediumData Structures

Description

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within an array.

Note: nums can contain negative numbers, so a plain sliding window does not work.

Example 1

Input: nums = [1,1,1], k = 2

Output: 2

Explanation: [1,1] (first two) and [1,1] (last two) both sum to 2.

Example 2

Input: nums = [1,2,3], k = 3

Output: 2

Explanation: [1,2] and [3] both sum to 3.

Example 3

Input: nums = [1,-1,0], k = 0

Output: 3

Explanation: [1,-1], [0], and [1,-1,0] all sum to 0.

Constraints

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

Subarray Sum Equals K: approach, complexity and pitfalls

A medium prefix sum problem, graded against 7 test cases (4 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Brute force checks all O(n^2) subarrays - think about prefix sums instead.
A subarray (i, j] sums to k exactly when prefixSum(j) - prefixSum(i) = k.
While scanning, keep a hash map of how many times each prefix sum has occurred; for the current sum S, add the count of (S - k) to the answer.

The optimal approach

Show the approach: Prefix Sums with a Hash Map

Let `S(j)` be the sum of the first `j` elements. A subarray ending at index `j` sums to `k` exactly when some earlier prefix `S(i)` equals `S(j) - k`. Scan once, maintaining a running sum and a hash map from prefix-sum value to its occurrence count (seeded with `{0: 1}` for subarrays starting at index 0). At each element, add `count[S - k]` to the answer, then record the current sum.

This handles negative numbers, which break sliding-window approaches.

Time: O(n) - single pass
Space: O(n) - the prefix-sum map

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.

← Back to problems

Subarray Sum Equals K

MediumData Structures

Description

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within an array.

Note: nums can contain negative numbers, so a plain sliding window does not work.

Example 1

Input: nums = [1,1,1], k = 2

Output: 2

Explanation: [1,1] (first two) and [1,1] (last two) both sum to 2.

Example 2

Input: nums = [1,2,3], k = 3

Output: 2

Explanation: [1,2] and [3] both sum to 3.

Example 3

Input: nums = [1,-1,0], k = 0

Output: 3

Explanation: [1,-1], [0], and [1,-1,0] all sum to 0.

Constraints

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

Subarray Sum Equals K: approach, complexity and pitfalls

A medium prefix sum problem, graded against 7 test cases (4 of them hidden).

The pattern: Prefix Sum

Precomputed cumulative totals so any range query becomes one subtraction.

Reach for it when you see: Repeated range-sum queries, or counting subarrays that sum to a target.

If you are stuck

Show the 3-step hint ladder

Brute force checks all O(n^2) subarrays - think about prefix sums instead.
A subarray (i, j] sums to k exactly when prefixSum(j) - prefixSum(i) = k.
While scanning, keep a hash map of how many times each prefix sum has occurred; for the current sum S, add the count of (S - k) to the answer.

The optimal approach

Show the approach: Prefix Sums with a Hash Map

This handles negative numbers, which break sliding-window approaches.

Time: O(n) - single pass
Space: O(n) - the prefix-sum map

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Prefix Sum mistakes

These apply to the pattern as a whole, not just this problem.

Not seeding the map with a zero-sum prefix, which loses every subarray starting at index 0.
Counting the current prefix before checking for its complement, so a zero-sum range matches itself.
Mixing inclusive and exclusive bounds between building the array and querying it - a consistent, invisible off-by-one.