560. 和为K的子数组（算法思维系列）

560. 和为K的子数组

• 题目
• 解题思路
• 代码

题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

解题思路

构造一个前缀和数组。presum[i]，就是nums[0..i-1]的和。

要找该数组中和为 k 的连续的子数组的个数。你就只需要直接去前缀和数组中找存在两个和相减等于k的即可。详情见书343。

代码

/*
这题其实可以用滑动窗口，但是复杂度太高了，会超时
*/
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        //k:前缀和，v：前缀和出现的次数
        Map<Integer,Integer> preSum=new HashMap<>();

        //第0个元素的前缀和为0
        preSum.put(0,1);

        int res=0;
        int sum=0;
        //构造前缀和
        for(int i=0;i<n;i++){
            sum=sum+nums[i];
            //sum_target就是我们要在前缀和数组中寻找的前缀和
            int sum_target=sum-k;

            if(preSum.containsKey(sum_target)){
                //有几个符合条件的前缀和，那么就有几种情况凑出k
                res =res+preSum.get(sum_target);
            }

            preSum.put(sum,preSum.getOrDefault(sum,0)+1);
        }

        return res;
    }
}