Approach - The frequency of all elements of the array is stored in a map. Then loop over all elements of the array, and on every step maintain a list of the sums of all subarrays ending at that position. This list of sums can be created by adding the current element to all existing sums, and afterwards adding the current element as a new sum to the list.
Example- for an array with elements [3,1,4…]. After third, before fourth step the list of sums will contain the elements [3+1+4,1+4,4].
So, on every loop we create an inner loop over the sums so far, and check using the frequency array how much elements with the sum exist, adding that number to ans. Set the frequency of an element to zero after having counted it once. Then it is counted as zero the next time.
My code-
#include <bits/stdc++.h>
using namespace std;
int count(int *v, int n, map<int,int>m)
{
int sum=0;
vectorlst;
lst.push_back(v[0]);
for(int i=1;i<n;i++)
{
for(int j=0;j<lst.size();j++)
{
lst[j]=lst[j]+v[i];
if(m.find(lst[j])!=m.end())
sum=sum+m[lst[j]];
m[lst[j]]=0;
}
lst.push_back(v[i]);
}
delete [] v;
return sum;
}
int main()
{
std::ios::sync_with_stdio(false);
int t,n,e,c;
cin>>t;
while(t–)
{
cin>>n;
int *v=new int[n];
map<int,int>m;
c=0;
for(int i=0;i<n;i++)
{
cin>>v[i];
m[v[i]]=m[v[i]]+1;
}
c=count(v,n,m);
std::cout << c << std::endl;
}
return 0;
}