Subarray Sum Equals K

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

1. 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.
2. 2Iterate through nums, adding each value to the running sum to get the current prefix sum S.
3. 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.
4. 4Increment count[S] by one so future positions can pair with the current prefix.
5. 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