We have an integer sequence A, whose length is N.
Find the number of the non-empty contiguous subsequences of A whose sums are 0. Note that we are counting the ways to take out subsequences. That is, even if the contents of some two subsequences are the same, they are counted individually if they are taken from different positions.
Constraints
1≤N≤2×105
−109≤Ai≤109
All values in input are integers.
Find the number of the non-empty contiguous subsequences of A whose sum is 0.
There are three contiguous subsequences whose sums are 0: (1,3,−4), (−4,2,2) and (2,−2).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+6;
int n;
ll d[maxn],ans;
map<ll,int>p;
int main()
{
cin>>n;
p[0]++;
for(int i=1;i<=n;i++)cin>>d[i];
for(int i=1;i<=n;i++){
d[i]=d[i]+d[i-1];
ans+=p[d[i]];
p[d[i]]++;
}
cout<<ans<<endl;
return 0;
}
