Leetcode 560

Coding question asked in Amazon interviews.

'''
nums = [1,2,3], k = 3

running sum map algorithm:
If the current sum from index 0 to i is 10
If there is a sum from index 0 to j is 7, and j < i,
then we can know from index i to j, the sum is 3

running sum map sums=dict()
key: sum from index 0 to index i
value: number of occurrence of this sum

running sum map sums={0: 1, 1: 1, 3: 1}
current number: 3
current sum from index 0 to current index: 6
the value to substract to get target 3: 3
total number of subarray: 2
'''
from collections import defaultdict
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        runningSumMap = defaultdict(int)
        runningSumMap[0] = 1

        currentSum = 0
        result = 0

        for num in nums:
            currentSum += num
            valueToSubstract = currentSum - k
            occurrences = runningSumMap[valueToSubstract]
            result += occurrences

            runningSumMap[currentSum] += 1

        return result