LeetCode百题【和为 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 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

解法

前缀和+哈希表
- 定义pre[i]为[0.....i]里所有数的和则有递推公式pre[i]=pre[i-1]+nums[i]
- 那么[j....i]和为k的的子数组条件可以转化为pre[i]-pre[j-1]=k
- 简单移项得:pre[j-1]=pre[i]-k
所以我们考虑以i结尾的和为k的连续子数组个数时只要统计有多少个前缀和为 pre[i]-k的pre[j]即可
我们建立哈希表以和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新哈希表边计算答案

class Solution {
    public  int subarraySum(int[] nums, int k) {
        int cnt=0;
        int pre=0;
        //<前缀和，出现次数>
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre+=nums[i];
            if (map.containsKey(pre-k)){
                cnt+=map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre, 0)+1);
        }
        return cnt;
    }
}