C++ O(n) solution with Queue


#1
int countlessthanequalto(vector<int> &A, int K)
{
    int n=A.size();
    int ans=0, s=0;
    queue<int> q;
    for(int i=0;i<n;i++)
    {
       s+=A[i];
       q.push(i);
       while(s>K)
       {
           ans+=q.size()-1;
           s-=A[q.front()];
           q.pop();
       }
    }
    while(!q.empty())
        ans+=q.size(),q.pop();
    return ans;
}

int Solution::numRange(vector<int> &A, int B, int C) {
    int ans=countlessthanequaltoA, C);
    if(B>0)
        ans-=countlessthanequalto(A, B-1);
    return ans;
}