子数组和等于目标值的个数问题

在这里插入图片描述

求解思路

这道题在遍历数组的过程中维护一个累加和sum，对于当前位置i，如果之前存在某个位置j使得0到j的前缀和等于sum-aim，那么j+1到i这段子数组的和就等于aim。

用哈希表记录每个前缀和出现的次数，每次查询sum-aim出现过多少次，就说明以当前位置结尾有多少个满足条件的子数组。

需要注意的是，在开始遍历前要先将0这个前缀和的出现次数设为1，这表示不选任何元素时前缀和为0，这样当sum本身就等于aim时也能正确统计。

举个栗子

假设数组为 [1, 2, 3]，目标值 aim = 3：

i=0, sum=1, 查找sum-3=-2(不存在)，ans=0，记录前缀和1
i=1, sum=3, 查找sum-3=0(存在1次)，ans=1，记录前缀和3
i=2, sum=6, 查找sum-3=3(存在1次)，ans=2，记录前缀和6

最终返回2，对应子数组 [3] 和 [1,2]。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public static int subarraySum(int[] nums, int aim) {
    HashMap<Integer, Integer> map = new HashMap<>();
    // 0这个前缀和，在没有任何数字的时候，已经有1次了
    map.put(0, 1);
    int ans = 0;
    for (int i = 0, sum = 0; i < nums.length; i++) {
        // sum : 0...i前缀和
        sum += nums[i];
        ans += map.getOrDefault(sum - aim, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return ans;
}

如果觉得有帮助，欢迎点赞、关注、转发~