leetcode-560：和为 K 的子数组

题目

题目连接

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

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

示例 2：

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

解题

方法一：前缀和（超时）

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        int n=nums.size();
        vector<int> preSums(n+1);
        for(int i=0;i<nums.size();i++){
    
            preSums[i+1]=preSums[i]+nums[i];
        }
        int count=0;
        for(int i=1;i<=n;i++){
    
            for(int j=0;j<i;j++){
    
                if(preSums[i]-preSums[j]==k){
    
                    count++;
                }
            }
        }
        return count;
    }
};

方法二：前缀和+哈希表

红色部分就是我们要求的和为k的子数组

如果当前遍历到的前缀和是presum，那么只要知道presum-k的个数就行了，对最后结果加上presum-k的个数
通过map去维护一个前缀和 的个数

class Solution {
    
public:
    int subarraySum(vector<int>& nums, int k) {
    
        unordered_map<int,int> map;
        map[0]=1;//前缀和为0的个数为1
        int preSum=0;
        int count=0;
        for(int num:nums){
    
            preSum+=num;
            if(map.count(preSum-k)){
    //加上前缀和为preSum-k的个数
                count+=map[preSum-k];
            }
            map[preSum]++;
        }
        return count;
    }
};