和为k的子数组

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

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

又是爷最爱的前缀和

暴力解法就不说了，懒得写一遍了反正有手就行

这种题目比较容易想到的是用前缀和求解，遍历数组，每次记录到当前元素的前缀和currSum。如果想要得到和为k的子数组，应该搜索之前数组中前缀和为currSum - k的数组个数，加上即可。为了得到之前遍历过程中找到的前缀和为currSum - k的数组个数，可以用哈希表来记录。

不过需要考虑当前前缀和就等于k的情况，所以需要事先给哈希表加入(0,1)的键值对，说明已经有一个前缀和为0的数组，即空数组。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> times;
        int currSum = 0, n = nums.size();
        int ans = 0;
        times[0] = 1;
        for(int i = 0; i < n; ++i){
            currSum += nums[i];
            int target = currSum - k;
            if(times.find(target) != times.end()){
                ans += times[target];
            }
            times[currSum]++;
        }
        return ans;
    }
};