和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2
输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2
输入：nums = [1,2,3], k = 3
输出：2

提示：

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

使用哈希表存储每个前缀和出现的次数

如果[j,i]这段区间和为k:sum[i]-sum[j-1]==k -> sum[i]-k==sum[j-1] 。

使用哈希表记录每个前缀和出现的次数，由于sum[j-1]先加入的哈希表，如果之后遍历到i，发现sum[i]-k也在哈希表中说明，[j,i]这段区间和为k.也就是当哈希表中存在sum[i]-k时就找到了满足条件的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int count  = 0;
        int sum = 0;
        map.put(0,1); //如果sum[i]==k -> sum-k = 0   -> map.get(0) == 1 
        for(int i =0;i<nums.length;i++){
            sum+=nums[i];
            count+=map.getOrDefault(sum-k,0);//以nums[i]为结尾的数组和等于k的个数等于sum[j-1]出现
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;
    }
}