O(n) correct solution with all invariants


#1

int Solution::numRange(vector &A, int L, int R) {
vector pref;
pref.push_back(0);
for(int i=0; i<(int)A.size(); i++) {
pref.push_back(pref[(int)pref.size() -1] + A[i]);
}

int le=-1, ri=-1 ;
int ans =0;
int sz = (int)pref.size();
for(int i=1; i<(int)pref.size(); i++) {
    while(le +1 <i &&  pref[i] - pref[le +1] >R) {
        le++;
    }
    while(ri  +1 < i && pref[i] -pref[ri +1]>L-1) {
        ri++;
    }
    ans+= max(0, i-le) -max(0, i-ri ) ;
}
return ans;

}