和为 K 的子数组

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

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

示例 1：

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

输出：2

示例 2：

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

输出：2

这是很经典、很重要的一道题，也是前缀和的经典题。

思路：用一个哈希表 mp 统计前缀和出现的次数。mp[sum] 代表前缀和为 sum 出现的次数。mp[sum - k] 代表和为 k 的子数组出现的次数。

比如假设当前前缀和 sum = 10，目标找到和为 4 （k = 4） 的子数组，只需要看前缀和 6 出现的次数。

int subarraySum(vector<int>& nums, int k) {
    int ans = 0;
    int sum = 0;
    
    unordered_map<int, int> mp;
    mp[0] = 1;
    
    for (int num : nums) {
        sum += num; // 前缀和
        if (mp.count(sum - k)) ans += mp[sum - k];
        mp[sum]++;
    }
    return ans;
}