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

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

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 **严格小于 **k 的 非空整数子数组数目 。

子数组 是数组中的一个连续元素序列。

示例 1：

**输入：** nums = [2,1,4,3,5], k = 10
**输出：** 6
**解释：**
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。 
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。

示例 2：

**输入：** nums = [1,1,1], k = 5
**输出：** 5
**解释：**
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= k <= 1015

双指针使用前提：

1. 子数组（连续）；
2. 有单调性。本题元素均为正数，这意味着只要某个子数组满足题目要求，在该子数组内的更短的子数组同样也满足题目要求。

做法：枚举子数组右端点，去看对应的合法左端点的个数，那么根据上面的前提 2，我们需要求出合法左端点的最小值。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度。
• 空间复杂度：O(1)。仅需要几个额外的变量。

[sol1-Python3]

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        ans = s = left = 0
        for right, num in enumerate(nums):
            s += num
            while s * (right - left + 1) >= k:
                s -= nums[left]
                left += 1
            ans += right - left + 1
        return ans

[sol1-Java]

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long ans = 0L, sum = 0L;
        for (int left = 0, right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k)
                sum -= nums[left++];
            ans += right - left + 1;
        }
        return ans;
    }
}

[sol1-C++]

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;
    }
};

[sol1-Go]

func countSubarrays(nums []int, k int64) (ans int64) {
	sum, left := int64(0), 0
	for right, num := range nums {
		sum += int64(num)
		for sum*int64(right-left+1) >= k {
			sum -= int64(nums[left])
			left++
		}
		ans += int64(right - left + 1)
	}
	return
}