Hint and easy soln


#1

using 3 pointers…k…j…i
sum between k to i will be <=C and from j to i will be <B, then ans+= j-k

Implementation:-
int Solution::numRange(vector &A, int B, int C) {
int sum=0,j=0,k=0,cnt=0,n=A.size();
for(int i=0;i<A.size();i++){
sum+= A[i];
while(sum>C and k<n){
sum-= A[k]; k++;
}
j = k;
int temp = sum;
while(temp>=B and j<n){
temp-= A[j];
j++;
}
cnt+= j-k;
}
return cnt;
}


#2

Thanks for such an elegant approach


#3

But what would the complexity be in the case of very small B and large C, (1,100) for example, wouldn’t you go move the pointer j up to i all the time, thus having O(n^2)?


#4

If k-i is less than C and j-i is less than B, how do you know j-k is between B and C? You’re taking something smaller than C and subtracting something smaller than B, the result can be smaller than B.