题目
Given an array of integers and an integer k,
you need to find the total number of continuous subarrays whose sum equals to k.
Input:nums = [1,1,1], k = 2
Output: 2
给定一个数组，找出连续元素构成的子数组中，和为k的数量。即 0 <= i <= j <= nums.length, sum[i,j] = k的情况数量。
分析
这道题很自然的可以想到sum[i,j] = sum[j] - sum[i-1]，可以构造一个sum数组，记录从0到i位的和，依次进行遍历计算sum[j] - sum[i]，这样的时间复杂度是O（n2）
一种比较好的方法是用一个map<sum, count>来记录和的值的出现次数，同时使用一个变量记录到目前为止的总和，sumj - sumi = k ==> sumj - k = sumi，每次找寻sumj -k在之前出现的次数，就是最后一个数字到j时候的可能次数。
因为最后需要的是情况总数，所以这样构造map，如果要求不一样，可以根据情况进行变化。
代码
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
Map<Integer, Integer> map = new HashMap<>(); //sum,count
map.put(0, 1);
int sum = 0;
int res = 0;
for(int i = 0; i < nums.length; ++i){
sum += nums[i];
res += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}