SuminArray.py

#### Dictionary

"""
Principle: If the cumulative sum of between 0 and i vs 0 and j is the same, the sum of elements lying in between i and j is 0

Extending this, If the difference cumulative sum UP TO two indices i and j is k (i.e. sum(....j)- sum(...i) = k), then sum(i...j) ==k

We use a dictionary to store to store cumulative sum up to all indices as key, WITH number of occurences as values i.e. (sum,count).

iterate for all nums in array, cumulating sums along the way

1. Every time a new sum is met, append according to above
2. Every time repeat sum met, increment count accordingly.
3. For every sum met, check count of sum-k exists in dictionary, as this will also determine number of times subarray with sum (k) has also occured in current index FOR THAT PARTICULAR UNIQUE CUMULATIVE SUM (of up to i).
Increment Count

4. Return total count

A defaultdict works exactly like a normal dict, but it is initialized with a function (“default factory”) that takes no arguments and provides the default value for a nonexistent key.

A defaultdict will never raise a KeyError. Any key that does not exist gets the value returned by the default factory.

Basically an idiot proof dict
"""


class Solution:
    
    #Dictionary solution
    def subarraySum(self, nums: 'List[int]', k: 'int') -> 'int':
        count = 0
        dictionary = collections.defaultdict(int)
        current_sum = 0
        for index, val in enumerate(nums):
        	current_sum += val
        	if current_sum == k:
        		count += 1
            
        	if current_sum - k in dictionary:
        		count += dictionary[current_sum - k]

        	dictionary[current_sum] += 1
        return count