A101794题解

$一.题意$

$求一个序列有多少子段之和为k$

$二.思路$

$看到子段第一时间想到的肯定是双指针，但是a_i可能小于0所以对于同一个左/右端点可能会有多个解，不可行$
$我们看到每个子段[l_i,r_i]的值都是\sum_{i=l_i}^{r_i}a[i]=a[l_i]+a[l_i+1]+a[l_i+2]+\cdots+a[r_i]，那我们必定能想到前缀和$
$设sum[i]是下标1至i中所有数的和，那么这段子段的值就是sum[r_i]-sum[l_i-1]$
$那对于每个r_i我们都找满足条件的sum[l_i]并计数不就可以了么$
$具体的，对于1\le r_i\le n我们要找的是1\le l_i < r_i且sum[r_i]-sum[l_i-1]=k即sum[l_i-1]=sum[r_i]-k$
$便可以用map存sum[l_i]在对于所有的i找sum[j]=sum[r_i]-k$
$注意因为j=l_i-1所以j可以为0$

$三.小练习$

#include <cstdlib>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
long long n,a[200050],k,sum[200050],ans;
map<long long,int>mp;
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    mp.insert(①);
    for (int i=1;i<=n;i++){
        long long tmp=sum[i]-k;
        if (mp.find(tmp)②mp.end()){
            ans+=mp[③];
        }
        if (mp.find(sum[i])④mp.end()){
            mp.insert(⑤);
        }
        mp[sum[i]]++;
    }
    cout<<ans;
	return 0;
}

①
$A.${0,0}
$B.${sum[1],1}
$C.${0,1}
$D.${sum[1],0}
②
$A.$<=
$B.$==
$C.$>=
$D.$!=
③
$A.$tmp
$B.$k
$C.$sum[i]
$D.$i
④
$A.$<=
$B.$==
$C.$>=
$D.$!=
⑤
$A.${sum[tmp],1}
$B.${sum[i],1}
$C.${sum[tmp],0}
$D.${sum[i],0}

$四.正解$

#include <cstdlib>
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
long long n,a[200050],k,sum[200050],ans;
map<long long,int>mp;
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    mp.insert({0,1});
    for (int i=1;i<=n;i++){
        long long tmp=sum[i]-k;
        if (mp.find(tmp)!=mp.end()){
            ans+=mp[tmp];
        }
        if (mp.find(sum[i])==mp.end()){
            mp.insert({sum[i],0});
        }
        mp[sum[i]]++;
    }
    cout<<ans;
	return 0;
}

$参考答案:CDABD$
$求点赞$