MediumArrayHash TablePrefix Sum

Subarray Sum Equals K

1 approach, code in every language

You are given an integer array nums and an integer k. Return the total number of contiguous subarrays whose elements add up to exactly k.

A subarray is a non-empty slice of consecutive elements. Note that the values may be negative and zero, so a longer subarray does not necessarily have a larger sum, and simply scanning for a growing window will not work.

Example 1

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

Output: 2

The subarrays [1,1] starting at index 0 and [1,1] starting at index 1 both sum to 2.

Example 2

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

Output: 2

The subarray [3] and the subarray [1,2] both sum to 3.

Constraints

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

Prefix Sum with Hash Map

Maintain a running prefix sum and use a hash map of prefix frequencies to count qualifying subarrays in one pass.

Loading animation…

Intuition

The sum of the subarray ending at index j and starting at index i equals prefix[j] - prefix[i - 1], where prefix is the running total of all elements seen so far. A subarray summing to k therefore corresponds to a pair of prefix values whose difference is exactly k. If the current running sum is S, then any earlier position whose prefix sum was S - k marks the start of a valid subarray. So instead of re-scanning, we keep a hash map that records how many times each prefix sum has occurred. At each element we look up how many earlier prefixes equal S - k and add that to the answer, then register the current prefix. Seeding the map with prefix 0 occurring once handles subarrays that start at index 0.

Algorithm walkthrough

1Initialize a hash map count with the entry {0: 1} so that a prefix equal to k is counted, and set the running sum and answer to 0.
2Iterate through nums, adding each value to the running sum to get the current prefix sum S.
3Add count[S - k] (default 0 if absent) to the answer; this counts every earlier prefix that lets the current position close a subarray summing to k.
4Increment count[S] by one so future positions can pair with the current prefix.
5After the loop, the accumulated answer is the number of subarrays that sum to k.

Implementation

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = {0: 1}
        running = 0
        answer = 0
        for num in nums:
            running += num
            answer += count.get(running - k, 0)
            count[running] = count.get(running, 0) + 1
        return answer

Time

O(n)

Space

O(n)

Each element is processed once; the hash map holds at most n + 1 distinct prefix sums.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Trail Elevation Stretches is our own problem on the technique behind Subarray Sum Equals K: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free