Q11: Subarray Sum Equals K. - DSA Patterns (Multi-Lang)

In Simple Words: Use prefix sums and a Hash Map storing frequency of prefix sums encountered so far. At each step, if currentPrefixSum - k is in the map, add its frequency to total count.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def subarraySum(nums: list[int], k: int) -> int:
    prefix_counts = {0: 1}
    curr_sum = 0
    count = 0
    for n in nums:
        curr_sum += n
        if (curr_sum - k) in prefix_counts:
            count += prefix_counts[curr_sum - k]
        prefix_counts[curr_sum] = prefix_counts.get(curr_sum, 0) + 1
    return count