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

统计得分小于 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。

解题思路

• 有一个误区，因为要计算[left, left]之间的元素和，想用sum函数求，但其实在枚举right的时候可以同时计算nums的和。

for right, num in enumerate(nums):
    sum += num

• ox3f, 本题元素均为正数，这意味着只要某个子数组满足题目要求，在该子数组内的更短的子数组同样也满足题目要求。也就是答案更新是如下所示：

ans += right - left + 1

• 当不满足条件的时候，移动左端点，直至条件满足。额8 5怕【4

    while s * (right - left + 1) >= k:
        s -= nums[left]
        left += 1
    ans += right - left + 1

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历数组一次。空间复杂度：O(1)。Σ为字符集合的大小，本题字符均为英文字母，所以Σ=52。注意left只会增加不会减少，left 每增加一次，我们就花费O(∣Σ∣)的时间。因为left至多增加m次，所以二重循环的时间复杂度为 O(Σm),总的时间复杂度为 O(Σm+n)。
• 空间复杂度：O(Σ)。如果创建了大小为128的数组，则Σ=128。