560. Subarray Sum Equals K

 [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)

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;
    }
}