DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Subarray Sum Equals K

mediumPrefix sum Must-do

Problem statement

Given an integer array nums (values may be negative) and an integer k, count how many contiguous, non-empty blocks of nums add up to exactly k. Blocks at different positions count separately, even if they contain the same values.

Examples

Example 1

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

Output: 4

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

Example 2

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

Output: 6

Explanation: Every one of the six blocks (three of length 1, two of length 2, one of length 3) sums to 0.

Hints

Approach

Use prefix sums with a hash map. Let run be the sum of everything up to the current index. A block ending here sums to k exactly when some earlier prefix sum equals run - k. So keep a map from each prefix sum to how many times it has occurred.

  1. Start the map with {0: 1}: the empty prefix, which lets a block that starts at index 0 be counted.
  2. For each number: add it to run. Add seen[run - k] (or 0) to the answer. Then increment seen[run].
  3. Return the answer.

Look up before inserting the current prefix, so a block is never matched against itself (which would count an empty block when k = 0).

ComplexityTime O(n)Space O(n)
Python
class Solution:
def subarraySum(self, nums: list[int], k: int) -> int:
seen = {0: 1} # prefix sum -> how many times it has occurred
run = 0
count = 0
for x in nums:
run += x
count += seen.get(run - k, 0) # earlier prefixes that leave exactly k
seen[run] = seen.get(run, 0) + 1
return count

Follow-up questions

  • Return the longest block that sums to k instead of the count.
  • Count blocks whose sum is divisible by k.

Frequently asked questions

It stands for the empty prefix before index 0. Without it, a block that starts at the very beginning of the array, such as [1, 2] in the first example, has no earlier prefix to match and is missed.

The window trick needs sums to grow as the window grows, which only holds for non-negative numbers. Here values can be negative, so the prefix-sum map is the general tool.

It is the same "running total plus hash map of what I've seen" idea as Two Sum, applied to ranges. A practical version: counting how many time spans have a net change of exactly zero, such as periods where instances launched and terminated balanced out.