leetcode 795. 区间子数组个数_ky0ma的博客-爱代码爱编程

模拟，计算贡献
以当前数字nums[i]为右端点，统计可能分为子数组的左端点。
nums[i]有三种情况：
1.大于right，此时不能作为右段点。
2.在[left, right]区间内此时可以作为右端点，此时可以分为的子数组至少为1，然后可以和之前连续的左端点继续分成新的数组。
3.小于left，此时可以作为右端点，但自己不能单独成为一个数组，需要符合要求的左端点，此时要看左边nums[i - 1]作为右端点可以分成的子数组个数，因为对于一个以nums[i - 1]为右端点的子数组来说，只要加上nums[i]即可成为新的数组

对于一个右端点来说nums[i]，如果nums[i]在[left, right]区间内，则它可以之前除大于right的数组成一个连续的数组，因此它可以和上一个符合要求的右端点nums[j]形成从子数组形成新的数组，也可以和在[j, i]之间的数形成新的连续数组（(j, i)中的数一定都是小于left的，一共有i - j个）。因此对于nums[i]，其可以分成的数组数 = nums[j] 可以组成的子数组数 + i - j

因此对于一个数nums[i]对结果的贡献：
如果nums[i]大于right，则无法组成子数组，贡献为0。
如果在[left, right]区间内则即可以与前一个符合区间的数nums[j] 在[left, right]组成的数组形成新的数组，也可以和他们之间的数(j, i)组成新的子数组，贡献为nums[j] 可以组成的子数组数 + i - j。
如果小于left，则只能和之前连续的数nums[i - 1]组成的子数组组成新的数组，贡献为nums[i - 1] 可以组成的子数组数

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int res = 0;
        int fro = 0, count = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > right)
            {
                fro = 0;
                count = 0;
                continue;
            }
            int cur = fro;
            if(nums[i] >= left)
            {
                cur += 1 + count;
                count = 0;
            }
            else
                count++;
            res += cur;
            fro = cur;
        }
        return res;
    }
};