> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/prefix-sum/560.-subarray-sum-equals-k.md).

# 560. Subarray Sum Equals K

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fmue4rrHiygeUPkmxJ8Ga%2F%E5%9C%96%E7%89%87.png?alt=media\&token=2b9cf51d-fb94-4640-867d-bb9424e15146)

```
 [1,1,1]
0 1 2 3

0, 1  -> find
1, 1  -> find
2, 1

 [1,2,3], k = 3
0 1

0, 1
1, 1
3, 1 ->find
6, 1 -> find

 [1,-1,0]  k = 0

0 1
1 1

find subarray = k = presum[x] - presum[y], 
so if presum[y] =  presum[x] - k, find it
```

```
why should we use map? why just use set? 

use set the count only 2, missing 1 count
in actuallay the beginning 0 is also a count, 
so we should use map to accumulate the count

ex: 
 [1 -1 0]     
0 1. 0 0   presum

k = 0
```

time: O(n)

space: O(n)

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int presum = 0;
        int count = 0;
        
        for (int i = 0 ; i < nums.length; i++) {
            presum += nums[i];
            if (map.containsKey(presum - k)) {
                count += map.get(presum - k);
            }
            map.put(presum, map.getOrDefault(presum, 0)+1);
        }
        return count;
    }
}
```