一个简单的哈希算法运用
不学哈希算法的有难了!

题解

首先明确题意是确定一段区间和是否为k
暴力解法应该是先求出sum前缀和数组然后O(n2)O(n^2)O(n2)判断$sum[r]-sum[l]==m$
我们把这个式子稍微改一改变成$sum[r]=m-sum[l]$
每次查询map添加$m-sum[l]$, 然后存储$sum[l]$作为下一次搜索中的$sum[r]$使用
还是有不懂的我推荐看这个视频然后再写这题简直是降维打击, 也就10分钟彻底了解哈希表问题怎么做
如果学完这题还意犹未尽还可以学学哈希字符串

代码

void solve()
{cin>>n>>m;vector<ll>a(n+1),b(a);map<ll,ll>mp;for(ll i=1;i<=n;i++) {cin>>a[i];b[i]=b[i-1]+a[i];}ans=0;mp[0]=1;//b[i]=m的情况也要算入在内for(ll i=1;i<=n;i++) {ans+=mp[b[i]-m];mp[b[i]]++;}cout<<ans<<endl;return;
}