leetcode 560 和为k的子数组（前缀和 + map）

题目描述：

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

题解：

　　一开始想着用双指针去写，仔细想想发现这里的数有正有负，在区间扩大的过程中，状态的变化不是单调的。

　　正解是优化的去枚举所有的区间。对于直接暴力的枚举，我们需要双重循环来遍历所有的区间，例如对于每个区间的右端点$i$，枚举所有的右端点$j$，通过前缀和的计算判断$(i,j)$这个区间是否满足题意。我们对右端点$j$的枚举做一个优化，实际上这里只需要知道对于左端点$i$而言，有多少个右端点$j$满足$pre[i] - pre[j] == k$，那么我们用一个$map$存一下前缀和的对应的次数，就可以$O(1)$的找出满住条件的右端点$j$个数。

AC代码：

　　

class Solution {
public:
    // 一般双指针的题目 需要有一个单调的状态变化
    //  用 hash 优化访问
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        if(len == 0) return 0;
        unordered_map<int,int> mp;
        int ans = 0;
        int sum = 0;
        for(auto num:nums)
        {
            sum += num;
            if(sum == k) ans++;
            if(mp.find(sum - k) != mp.end()) ans += mp[sum-k];
            mp[sum]++;
        }
        return ans;
    }
};