[数据结构与算法]LeetCode.和为k的子数组（前缀和+哈希表）

题目描述：560. 和为 K 的子数组 - 力扣（LeetCode） (leetcode-cn.com)

?思路：前缀和：预处理求出s[1~n]，然后就能快速求出任意数组任意区间里一段数的和，如求l~r区间的和，就是s[r]-s[l-1]，但是如果求出前缀和再求任意子区间的和时间复杂度就是O(N*N)，让求任意子区间的和是否为k，即i~j子区间s[j]-s[i]=k，那么我们可以换一个思路，找满足值为s[j]-k的s[i]的有多少个(因为s[j]-k如果等于s[i]，则说明从i-1到j这一段子数组的和为k)，即遍历所有以j结尾的前缀和，看看是否存在值为s[j]-k的值存在，但怎么判断是否有这样的前缀和存在呢，为了将时间复杂度缩小到O(N)，可以借助一个哈希表，键值是以j结尾的区间的和，键对应的值是该区间和出现的次数，这样在找是否有这样的前缀和存在，存在多少个的复杂度就是O(1)。空间其实可以优化，我们并不需要一个前缀和数组，因为每次求的前缀和之和前一个前缀和有关，所以用一个pre变量来保存当前下标 j 的前缀和就可以，然后再哈希表里找，是否存在一个以 i 为下标的前缀和满足s[j]-k=s[i]，如果存在，计数变量加上该前缀和存在的次数，并且每次都要将该次计算的前缀和存入哈希表。

代码实现C++:

int subarraySum(vector<int>& nums, int k) {
        int pre=0,count=0;
        unordered_map<int,int> mp;
        mp[0]=1;//初始化表示前缀和为0的出现次数为1
        for(auto num:nums){
            pre+=num;
            if(mp.find(pre-k)!=mp.end()){//如果查找满足条件的前缀和存在
                count+=mp[pre-k];//计数
            }
            mp[pre]++;//将前缀和存入哈希表
        }
        return count;
    }