统计得分小于K的子数组数目

一个数组的分数定义为数组之和乘以数组的长度

1. 前缀和 + 二分

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        //注意是正整数数组
        int n = nums.size();
        long long res = 0;
        vector<long long> presum(n+1);
        for(int i=0;i<n;i++)
            presum[i+1] = presum[i] + nums[i];
        for(int i=0;i<n;i++){
            int left = i; int right = n;
            while(left<right){
                int mid = (left+right+1)/2;
                long long cur = presum[mid]-presum[i];//当前区间和
                if(cur*(mid-i)>=k)  right = mid-1;
                else left = mid;
            }
            res+=(left-i);
        }
        return res;
    }
};

2. 双指针

由于都是正数，所以可以贪心的移动右指针

class Solution {
public:
    long long countSubarrays(vector<int> &nums, long long k) {
        long ans = 0L, sum = 0L;
        for (int left = 0, right = 0; right < nums.size(); ++right) {
            sum += nums[right]; //累计当前区间和
            while (sum * (right - left + 1) >= k)//移动左指针至满足条件
                sum -= nums[left++];//移动后扣除前面的
            ans += right - left + 1;//计数
        }
        return ans;
    }
};