Subarray Sum Equals K

Intuition

Solution

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