哈希表+前缀和

适用情况：求满足一定性质的数组区间（或者是树的路径），此时因为数组中有正有负，不能使用滑动窗口。

板子：

#include<iostream>
#include<unordered_map>
 
int hashsum(vector<int> &nums,int k){
        unordered_map<int,int> m;//用来存储前面出现的前缀和
        m.insert({0,1});//初始化一个前缀和为0的数
        int count=0,pre=0;
        for(auto &x:nums){
            pre+=x;
            if(m.find(pre-k)!=m.end()){//因为pre+x=k，所以我们要查询前面有多少个pre-k的组合
                count+=m[pre-k];
            }
            m[pre]++;
 
        }
       return count;
 
}

复杂度分析：

时间空间都为O（n）

例题：

剑指II 10,50;