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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 2 * 10(4)

-1000 <= nums[i] <= 1000

-10(7) <= k <= 10(7)

暴力解法是遍历数组做第一个元素，再遍历后续元素分别做最后一个元素

在此基础上可以考虑用前缀和数组进行优化，求和时只需sum[i]-sum[j]=k

将上述式子移项有，sum[i]-k=sum[j]

也就是说当第i个元素做最后一项时，前面的项只要前缀和为sum[i]-k就可以作为第一个元素

所以我们可以遍历数组，分别做最后一个元素，

然后求前缀和，加上满足条件的前缀和出现的次数，再更新前缀和频率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int> &nums, int k) {
        int len = nums.size();
        unordered_map<int, int> count;
        count[0] = 1;
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < len; i++) {
            pre += nums[i];
            ans += count[pre - k];
            count[pre]++;
        }
        return ans;
    }
};