# Subarray Sum Equals K\*

```python
class Solution:
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        """
        背後原理:
        假設我們有 csumKey1 = cumulativeSum [i]為 nums[0] +...+ nums[i]的總和
        且我們現在有 csumKey2 = cumulativeSum[j]: nums[0] + ... + nums[i] + ... nums[j]
        若 csumKey2 - k = csumKey1 則我們可以宣稱找到一連續數和為 K
        註: 
        若array中的元素皆為"非負整數" 則我們可以說 nums[i+1]~ nums[j] 的累加值為 k
        若有負數則此法會無法知道 index 確切位置    
        
        Example: [3, 4, 7, 2, -3, 8] k = 7
        index:    1  2  3  4   5  6
        cSum:     3  7  14 16  11 19
                     ^ 
                  這裡我們意識預先給 csumKey = 0 的值: {0:1} 然後宣稱找到第一個累加值為7
        當 index = 3 時 我們把累加值減去 k : 14 - 7 = 7 然後去找是否有先前累加值為7的cSumkey
        我們找到先前 cSumKey = 7 (index = 2) 此時我們可以宣稱找到一連續subarray累加值為 7          
        """
        my_dict = {0:1}
        csum = 0
        res = 0
        for num in nums:
            csum += num            
            res += my_dict.get(csum-k, 0)
            my_dict[csum] = my_dict.get(csum, 0) + 1      
        return res
```
