class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
"""
s[i] = sum(nums[:i])
s[j] - s[i] = sum(nums[i:j])
"""
ans = 0
s = {0:1}
prev = 0
for num in nums:
prev += num
if prev - k in s:
ans += s[prev - k]
if prev not in s:
s[prev] = 0
s[prev] += 1
return ans