LC 560: Subarray Sum Equals K

Problem: Given an integer array nums (can contain negatives and zeros) and an integer k, count the contiguous subarrays whose sum equals k.

1. Algorithm

Prefix sum + hash map.

Let prefix[j] be the sum of the first j elements. The sum of the subarray (i, j] is prefix[j] - prefix[i]. We want that to equal k, so for each j we need to count earlier indices i where:

prefix[i] = prefix[j] - k

So while scanning left to right, we keep a hash map of how many times each prefix sum has occurred so far. At each position, we look up current_prefix - k and add its count to the answer.

Invariant: Before processing index j, the map holds counts of every prefix sum for indices < j (including the empty prefix 0).

Why not sliding window? Sliding window needs monotonicity (extending the window only increases the sum). Negatives break that, so we can’t decide when to shrink. The hash map approach has no such restriction.

2. Python solution

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = defaultdict(int)
        count[0] = 1              # empty prefix
        prefix = 0
        ans = 0

        for x in nums:
            prefix += x
            ans += count[prefix - k]
            count[prefix] += 1

        return ans