一个数组的分数定义为数组之和乘以数组的长度
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;
}
};