Sliding Window with 10 lines of code


#1

int calc(vector&A,int X)
{
int n=A.size();
int st=0;
int end=0;
int s=0;
int count=0;
while(end<n)
{
s+=A[end];
while(st<=end&&s>=X)
{
count+=(n-end);
s-=A[st];
st++;
}
end++;
}
return count;
}

int Solution::numRange(vector &A, int B, int C) {
int n=A.size();

int countB=0;

int countC=0;

countB=calc(A,B);  // Total subarrays of sum>=B
countC=(n*(n-1))-calc(A,C+1); // total subarrays of sum<=C

return countB+countC-(n*(n-1));  // n(A^B)=n(A)+n(B)-n(AXB);

}