# 560. Subarray Sum Equals K

[Link](https://leetcode.com/problems/subarray-sum-equals-k/)

**Solution**

跟&#x20;

1. Two Sum
2. Path Sum III

概念類似都是透過map紀錄每個歷史sum值以及出現次數

查找map中的currentSum - K出現次數， 就可以知道 以目前的currentNode結尾且sum = k的subarray次數

```
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ret = 0;
        int cur = 0;
        for(int i = 0; i < nums.length; i++){
            cur += nums[i];
            ret += map.getOrDefault(cur - k, 0);
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }
        
        return ret;
    }
```

&#x20;\*\*Complexity Analysis\*\*

* Time complexity : O(n)O(n). The entire numsnums array is traversed only once.
* Space complexity : O(n)O(n). Hashmap map can contain upto nn distinct entries in the worst case.
