leetcode区间子数组个数_统计完全子数组的数目

1.暴力法

效率低，超时

2.计数

计算数组中所有元素小于等于R的子数组的数量和所有元素小于等于L-1的子数组的个数，然后相见即可

对于数组A，计算所有元素小于等于num的子数组的数量可以在O(n)完成

设ans 为总数，cur为包含当前元素且满足要求的子数组个数

遍历数组A，对于每一个元素A[i],如果A[i]<=num,则cur+1,否则cur=0,然后领ans+=cur,

手动模拟如下：

如1 2 1 3 4 2 3  num=3

初始ans=0,cur=0;

A[0]=1<3,cur=1,ans=ans+cur=0+1=1,子数组为1

A[1]=2<3,cur=cur+1=2,ans=ans+cur=1+2=3,新增子数组为2，1 2

A[2]=1<3,cur=cur+1=3,ans=ans+cur=3+3=6,新增子数组为3，2 3，1  2 3

A[3]=3=3,cur=cur+1=4,ans=ans+cur=6+4=10,新增子数组为3，1 3，2 1 3，1 2 1 3

A[4]=4>3,cur=0,ans=ans+cur=6+0=6,新增子数组为0

A[5]=2<3,cur=cur+1=1,ans=ans+cur=10+1=11,新增子数组为2

A[6]=3=3,cur=cur+1=2,ans=ans+cur=11+2=13,新增子数组为3，2 3

代码如下：

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& A, int L, int R) {
       return count(A,R)-count(A,L-1);
    }
    int count(vector<int> &A,int num)//所有元素都小于等于num的子数组的数量
    {
        int ans=0, cur=0;
        for(int i=0;i<A.size();i++)
        {
            cur=A[i]<=num?cur+1:0;
            ans+=cur;
        }
        return ans;
    }
};