前缀和

作者:江月迟迟

发表于:2024-12-20

字数统计:118 字

预计阅读1分钟

713. 乘积小于 K 的子数组

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
//  前缀和
var countSubarrays = function(nums, k) {
    nums.unshift(0)
    let ans = 0
    const prefixSum = Array(nums.length).fill(0)
    for(let i = 0; i < nums.length-1; i++) {
        prefixSum[i+1] = prefixSum[i] + nums[i+1]
    }
    // 还是只能二分查找
    for(let i = 0; i < nums.length; i++) {
        let left = 0, right = i, mid
        while(left <= right) {
            mid = (left + right) / 2 | 0
            if((prefixSum[i] - prefixSum[mid]) * (i - mid) >= k) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        ans += i - left
    }
    return ans
};