Prerequisite :- Prefix Sum.
Explanation :-
Given a subarray from L to R is considered good if its sum is equivalent to its length.
Iterate from Lth to Rth element to find the sum of the range.
Use prefix sum to optimize the previous step, find the sum of range in O(1) time using prefix array.
Pi represents the prefix sum till the ith index.
So according to the problem Pj - Pi = j - i, so Pi - i = Pj - j.
Group prefix by value Pi - i for i from 0 to n, If we have n prefix with same value Pi - i then we have to add Pi - i to our answer.
C++ Solution :-
#include <bits/stdc++.h>
using namespace std;
void solve(){
long long n;
long long fans = 0;
cin>>n;
vector<int>v(n,0);
for(int i = 0;i<n;i++){
cin>>v[i];
}
map<long,long>m1;
vector<long long>pre(n+1,0);
int sum = 0;
m1[0] = 1;
for(int i = 1;i<=n;i++){
sum += v[i-1];
fans += m1[sum-i];
m1[sum-i]++;
}
cout<<fans<<"\n";
}
int main() {
int freq = 1;
while(freq--){
solve();
}
// your code goes here
}