Back to Problem
Official 453 views

Editorial: Subarrays Summing to K

by admin ·

12

1 Intuition

A subarray (i, j] sums to k exactly when prefix[j] - prefix[i] = k.

2 Approach

Scan once, keeping a hash map of how many times each prefix sum has occurred; for each new prefix add the count of prefix - k.

3 Complexity Analysis

Time O(n), Space O(n).

4 Solution Code 

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

5 Code Walkthrough

The reference solution below implements the approach step by step.