Simple O(n) solution in C++


#1

int Solution::solve(vector &A, int B) {

int s=0,e=0,ans=0;
int n=A.size();
int sum=A[0];

while(s<n && e<n)
{
    if(sum<B)
    {
        e++;
        ans+= max(0,e-s);
        sum+= A[e];
    }
    if(sum>=B)
    {
        sum-= A[s];
        s++;
    }
}
return ans;

}


#2

Hey Bro ,
why you add ans+=max(0,e-s);
thanks


#3

That’s not really necessary. I just wanted to be sure that I am not adding negative value to ‘ans’.
Writing only ans+= e-s should also suffice.


#4

I am asking why you are doing e-s.
I know I have to count subarrays, We cannot do ans++. But Why “e-s” ?


#5

nice code !!
corner cases are automatically covered.


#6

because we have to count all subarrays that end at e ,that start from s, s+1 ,s+2 … <e