###### tags: `Leetcode` `medium` `array` `hash` `prefix sum` `python` `c++` `Top 100 Liked Questions`

# 560. Subarray Sum Equals K

## [題目連結:] https://leetcode.com/problems/subarray-sum-equals-k/

## 題目:
Given an array of integers ```nums``` and an integer ```k```, return the total number of subarrays whose sum equals to ```k```.

A subarray is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

Input: nums = [1,1,1], k = 2
Output: 2

**Example 2:**

Input: nums = [1,2,3], k = 3
Output: 2

## 解題想法:
* 此題為求數組中有多少個連續子數組的和等於k
* 使用hash table紀錄前綴和
* dic:
* key:當前數字+之前的數組的總和
* val:此總和出現次數
* 通過每次用當前位置累計的部分和totalSum
* **去找尋字典中key為totalSum-k是否存在**
* 若存在: 表示多了dic[totalSum-k]種可以總和為k的情況
* 解釋: 即對於每個位置的值，皆求以該位置為結尾且**和為K的區間**的個數，並更新res
* 因為字典紀錄了各位置的連續和
* 所以res紀錄每個連續區間是否可以扣掉前面的其他連續區間得到總和為K

* trace:

ex: nums=[1, 3, 1, 4, -4], k=4
總共組合數應該要有4個
(1,3)、(3,1)、(4)、(3,1,4,-4)

    num=    1    3    1    4    -4
部分和:  0   1    4    5    9    5

dic: key紀錄部分和、val紀錄出現數量
初始:     dic[0]=1
nums=1:  dic[1]=1
nums=3:  因為此時部分和為4，4-k=0，dic[0]存在，所以res+=dic[0],且dic[4]=1
nums=1:  因為此時部分和為5，5-k=1，dic[1]存在，所以res+=dic[1],且dic[5]=1
nums=4:  此時部分和為9, 9-k=5，dic[5]存在，所以res+=dic[5], 且dic[9]=1
nums=-4: 此時部分和為5, 5-k=1, dic[1]存在，所以res+=dic[1], 且更新dic[5]=2

例如 nums[2]=1 ，其部分和為5
所以需要找5-k=1，dic[1]=1: 表示前面區間和為1的區間有1個，即開頭的nums[0]=1
所以區間nums[1]、nums[2]: [3,1]即為一組和為k的解

## Python:

from collections import defaultdict
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        #dic的key為該位置+之前的數組的總和 val為出現次數
        #sum累加所有數 每到一個新位置 往dic找sum-k是否存在 
        dic=defaultdict(int)
        res=0 #出現次數
        totalSum=0
        dic[0]=1 #初始: 和為0:啥都不加入 出現1次
        for val in nums:
            totalSum+=val
            if totalSum-k in dic:
                res+=dic[totalSum-k]
            dic[totalSum]+=1
        print(dic)
        return res
        
nums=[1,3,1,4,-4,4]
k=4
result=Solution()
ans=result.subarraySum(nums,k)
print(ans)

## C++:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> dic={{0, 1}};
        int res=0, curSum=0;
        for (int val: nums){
            curSum+=val;
            if (dic.count(curSum-k)) //exist in dic
                res+=dic[curSum-k];
            dic[curSum]+=1;
        }
        return res;
    }
};