from collections import defaultdict


class Solution:
    # O(n) time
    # O(n) space
    def subarraySum(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0

        cur_sum = 0
        count = 0
        # or counter.count(nums)
        sum_to_count = defaultdict(int)
        sum_to_count[0] = 1
        for num in nums:
            cur_sum += num
            count += sum_to_count[cur_sum - k]
            sum_to_count[cur_sum] += 1

        return count
03315e26a3694d2a8db40b7e3888f7a4b9ac8387
<mask token>

<mask token>


class Solution:
    <mask token>

<mask token>


class Solution:

    def subarraySum(self, nums: List[int], k: int) ->int:
        if not nums:
            return 0
        cur_sum = 0
        count = 0
        sum_to_count = defaultdict(int)
        sum_to_count[0] = 1
        for num in nums:
            cur_sum += num
            count += sum_to_count[cur_sum - k]
            sum_to_count[cur_sum] += 1
        return count

from collections import defaultdict


class Solution:

    def subarraySum(self, nums: List[int], k: int) ->int:
        if not nums:
            return 0
        cur_sum = 0
        count = 0
        sum_to_count = defaultdict(int)
        sum_to_count[0] = 1
        for num in nums:
            cur_sum += num
            count += sum_to_count[cur_sum - k]
            sum_to_count[cur_sum] += 1
        return count

from collections import defaultdict


class Solution:
    # O(n) time
    # O(n) space
    def subarraySum(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0

        cur_sum = 0
        count = 0
        # or counter.count(nums)
        sum_to_count = defaultdict(int)
        sum_to_count[0] = 1
        for num in nums:
            cur_sum += num
            count += sum_to_count[cur_sum - k]
            sum_to_count[cur_sum] += 1

        return count