LeetCode 560 和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。

思路：

根据题目连续子数组和 --> 前缀和。

利用hashmap存储前缀和与其出现的次数。

从前往后遍历前缀和数组：

由sum[right] - sum[left] == k（后 - 前)得知判断hashmap里是否存在sum[i] - k，累加其出现的次数;以及特判一下当前的sum[i]是否 == k。

最后将sum[i]存进hashmap中。

代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] sum = new int[nums.length + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int count = 0;
        Map<Integer,Integer> map = new HashMap();
//        r - l == k
        for (int i = 1; i < sum.length; i++) {
            if (sum[i] == k ){
                count++;
            }
            if (map.containsKey(sum[i] - k)){
                count += map.get(sum[i] - k);
            }
            if (map.containsKey(sum[i])){
                map.put(sum[i],map.get(sum[i]) + 1);
            }else {
                map.put(sum[i],1);
            }
        }

        return count;
    }
}