<reponame>Linchin/python_leetcode_git<gh_stars>0
"""
Q560
Subarray Sum Equals K
Medium

Array; Hash Table.

Running sum;
O(n).

Given an array of integers and an integer k, you need to find the
total number of continuous subarrays whose sum equals to k.

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range
of the integer k is [-1e7, 1e7].
"""

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:

        # method 2: presum + hash
        mem = {0: 1}
        s = 0
        total = 0
        for i in range(len(nums)):
            s += nums[i]
            if s - k in mem:
                total += mem[s-k]
            if s not in mem:
                mem[s] = 1
            else:
                mem[s] += 1

        return total


nums = [1,-1,0]
k = 0
sol = Solution()
print(sol.subarraySum(nums, k))









"""
Q560
Subarray Sum Equals K
Medium

Array; Hash Table.

Running sum;
O(n).

Given an array of integers and an integer k, you need to find the
total number of continuous subarrays whose sum equals to k.

Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range
of the integer k is [-1e7, 1e7].
"""

from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:

        # method 2: presum + hash
        mem = {0: 1}
        s = 0
        total = 0
        for i in range(len(nums)):
            s += nums[i]
            if s - k in mem:
                total += mem[s-k]
            if s not in mem:
                mem[s] = 1
            else:
                mem[s] += 1

        return total


nums = [1,-1,0]
k = 0
sol = Solution()
print(sol.subarraySum(nums, k))
Q560 Subarray Sum Equals K Medium  Array; Hash Table.  Running sum; O(n).  Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.  Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7]. # method 2: presum + hash