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
解释：
得分小于 10 的 6 个子数组为：
- [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 <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= 10^15

解题思路

这道题要求计算得分小于 k 的子数组数目，其中得分定义为子数组元素和乘以子数组长度。

核心思路：

  1. 暴力解法：枚举所有可能的子数组，计算每个子数组的得分并统计符合条件的数量。时间复杂度为 O(n³)，对于大规模数据会超时。

  2. 滑动窗口优化：使用双指针技术，维护一个滑动窗口 [left, right]。关键观察是：

    • 如果子数组 [left, right] 的得分 >= k，那么所有包含这个子数组的更长子数组的得分也会 >= k
    • 因此可以用双指针维护最大的符合条件的窗口

  3. 算法流程：

    • 使用 left 和 right 两个指针，维护当前窗口的元素和 sum
    • 当窗口 [left, right] 的得分 >= k 时，收缩左边界
    • 当窗口 [left, right] 的得分 < k 时，以 right 为右端点的所有子数组 [left, right], [left+1, right], …, [right, right] 都满足条件
    • 每次 right 右移时，新增的满足条件的子数组数量为 (right - left + 1)

推荐解法：滑动窗口 时间复杂度 O(n)，空间复杂度 O(1)，是最优解法。

代码实现

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        int n = nums.size();
        long long result = 0;
        long long sum = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            // 当前窗口得分 >= k 时，收缩左边界
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            
            // 以 right 为右端点的符合条件的子数组数量
            result += right - left + 1;
        }
        
        return result;
    }
};

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        result = 0
        sum_val = 0
        left = 0
        
        for right in range(n):
            sum_val += nums[right]
            
            # 当前窗口得分 >= k 时，收缩左边界
            while sum_val * (right - left + 1) >= k:
                sum_val -= nums[left]
                left += 1
            
            # 以 right 为右端点的符合条件的子数组数量
            result += right - left + 1
        
        return result

public class Solution {
    public long CountSubarrays(int[] nums, long k) {
        int n = nums.Length;
        long result = 0;
        long sum = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            
            // 当前窗口得分 >= k 时，收缩左边界
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            
            // 以 right 为右端点的符合条件的子数组数量
            result += right - left + 1;
        }
        
        return result;
    }
}

var countSubarrays = function(nums, k) {
    const n = nums.length;
    let result = 0;
    let sum = 0;
    let left = 0;
    
    for (let right = 0; right < n; right++) {
        sum += nums[right];
        
        // 当前窗口得分 >= k 时，收缩左边界
        while (sum * (right - left + 1) >= k) {
            sum -= nums[left];
            left++;
        }
        
        // 以 right 为右端点的符合条件的子数组数量
        result += right - left + 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型滑动窗口解法
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：每个元素最多被访问两次（一次被右指针访问，一次被左指针移出），因此总时间复杂度为 O(n)
  • 空间复杂度：只使用了常数个额外变量，空间复杂度为 O(1)

相关题目