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

标签: 数组 二分查找 前缀和 滑动窗口

难度: Hard

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

  • 比方说，[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

Submission

运行时间: 135 ms

内存: 28.0 MB

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

Explain

这是一道使用双指针技术解决的问题。我们初始化两个指针left和right，分别代表子数组的左右边界。我们从左到右遍历数组，每次将right指向的元素加到当前的分数中，然后检查当前子数组的分数是否小于k。如果分数大于或等于k，我们就移动left指针，直到分数再次小于k。每次迭代中，以right为右端点的符合条件的子数组数量就是right - left + 1，我们将这个值累加到最终答案中。

时间复杂度: O(n)

空间复杂度: O(1)

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

Explore

是的，题解中的策略是每次向子数组中添加一个新元素（即右移right指针），然后检查当前子数组的得分乘以长度是否大于或等于k。如果是，这意味着当前的子数组不符合条件，需要通过右移left指针来减少子数组的长度和得分，直到子数组的得分乘以长度再次小于k。因此，只有在添加新元素后导致总得分超过k时，我们才调整left指针，以尝试找到一个有效的子数组。

使用累加方式更新score而不是每次重新计算子数组的和是为了提高算法的效率。如果每次重新计算，则每次移动指针时的时间复杂度为O(n)，这会使得整体算法的时间复杂度变得很高。通过累加方式更新，我们可以在O(1)的时间内更新score，从而保持整体算法的时间复杂度为O(n)。这种方法通常不会导致错误，只要我们正确地在移动左指针时减去左端点的值。如果忘记在移动左指针时更新score，那么计算结果将会错误。

这种方法在数值非常大的情况下仍然有效，因为它依赖的是数学条件的正确性：只要子数组的得分乘以长度大于或等于k，就需要减小子数组的大小。然而，在实际的计算机程序中，特别是在处理非常大的数值时，需要注意整数溢出的问题。在某些编程语言中，得分和长度的乘积可能超过整数类型的最大值，导致溢出。在这种情况下，可以考虑使用更大范围的整数类型或适时地进行类型转换。

是的，题解中的算法考虑了所有子数组的边界条件。算法从每个可能的右端点开始，逐步尝试包含不同长度的子数组，从最小的子数组（只包含一个元素）到最大可能的子数组（从当前left到right的全部元素）。算法通过动态调整left和right指针来确保每个子数组都被计算和考虑，因此它涵盖了从最小到最大的所有子数组。