560. Subarray Sum Equals K

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = defaultdict(int) # times we've seen a prefix sum
        count[0] = 1
        prefix = 0 # running sum
        total = 0
        # add mile markers to find some subarray such that we can get a thing of length k
        # we know that it exists because we stored all sums thus far
        for num in nums:
            prefix += num
            # At each, index, we ask: how many different starting points have I seen
            # that would make a valid subarray ending here?

            # We care when there's an interval with sum k
            total += count[prefix - k] # how many subarrays end here?
            count[prefix] += 1
        return total

        # count = {0: 1}
        # prefix = 0
        # total = 0

        # for num in nums:
        #     prefix += num
        #     total += count.get(prefix - k, 0)
        #     count[prefix] = count.get(prefix, 0) + 1
        # return total