官方题解

题目大意

给定一个长度为 $n$ 的数组和一个整数 $k$ ，求数组 $a$ 的所有连续子序列中，元素之和等于 $k$ 的个数。

解题思路

首先我们可以预处理前缀和数组 $s$ ，即需要求区间满足 $s_r-s_{l-1}=k$ 的区间个数。问题就转化成了非常经典的问题。

枚举区间右端点 $r$ ，同时统计已枚举前缀每个 $s_l$ 的个数，那么对于这个 $r$ ，对答案贡献为满足 $s_{l-1} = s_r - k$ 的所有 $l$ 的个数。那么问题又进一步简化为：统计 $s_i = x$ 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。

参考代码

方法一：map

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

ll a[N], s[N];

int main(){
    ll n,k;cin>>n>>k;
    map<ll,ll>cnt;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    cnt[0]=1;
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=cnt[s[i]-k];
        cnt[s[i]]++;
    }
    cout<<res<<endl;
    return 0;
}

方法二：离散化

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

ll a[N],s[N];
ll all[N*2];
ll cnt[N*2];
int idx;

int find(ll x,int sz) {
    return lower_bound(all,all+sz,x)-all;
}

int main(){
    ll n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    for(int i=0;i<=n;i++){
        all[idx++]=s[i];
        all[idx++]=s[i]-k;
    }
    sort(all,all+idx);
    int m=unique(all,all+idx)-all;
    
    int pos=find(0,m);
    cnt[pos]=1;
    ll res=0;
    for(int i=1;i<=n;i++) {
        int pos=find(s[i]-k,m);
        res+=cnt[pos];
        
        pos=find(s[i],m);
        cnt[pos]++;
    }
    cout<<res<<endl;
    return 0;
}