560. 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.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找 前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

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