力扣(LeetCode)795. 区间子数组个数(C++)

模拟

有一种构想，只考虑上边界，在小边界和大边界之间的连续子数组个数 $=$小于等于大边界的连续子数组个数 $-$ 小于小边界的连续子数组个数。

连续子数组个数计算公式 $sum=\frac{n\times (n+1)}{2}$
长度为 $n$ 的小于某上界的区间，我们可以从中取 $n/(n-1)/(n-2)\dots /2/1$ 个数，构成连续子数组，分别有 $1/2/3\dots /(n-1)/n$ 个数组，总共 $\frac{n\times (n+1)}{2}$ 个连续子数组。

统计 $nums$ 所有区间，分别求出连续子数组个数， $ans=\sum sum$ 就是 $nums$ 内所有连续子数组个数。

提示 : 文中所有公式成立的前提是只考虑小于某边界。

C++

class Solution {
public:
    int calc(vector<int> &nums,int k){
        int ans = 0;
        for(int i= 0;i<nums.size();i++){
            if(nums[i]>k) continue;
            int j = i+ 1;
            while(j<nums.size()&&nums[j]<=k) j++;
            ans += (long long)(j-i)*(j-i+1)/2;
            i = j;
        }
        return ans;
    }
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return calc(nums,right) - calc(nums,left -1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度 $O(n)$ : 一次遍历 $nums$ 即可求出小于某边界的连续子数组个数，遍历较大边界和较小边界的总时间复杂度 $O(2\times n)$ ，忽略常数时间复杂度 $O(n)$ 。

空间复杂度 $O(1)$ : 只用到常量级空间。

致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC