跳转至

剑指 Offer II 009. 乘积小于 K 的子数组

题目描述

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

 

示例 1:

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

输入: nums = [1,2,3], k = 0
输出: 0

 

提示: 

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

 

注意：本题与主站 713 题相同：https://leetcode.cn/problems/subarray-product-less-than-k/ 

解法

方法一：滑动窗口

我们使用滑动窗口维护一个乘积不超过 $k$ 的连续子数组。每次右边界 $j$ 向右移动一位，如果乘积超过了 $k$，则左边界 $i$ 向右移动，直到乘积小于 $k$。那么以右边界 $j$ 为结尾的子数组个数为 $j - i + 1$，我们将其累加到答案中。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        s = 1
        ans = i = 0
        for j, x in enumerate(nums):
            s *= x
            while i <= j and s >= k:
                s //= nums[i]
                i += 1
            ans += j - i + 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        long s = 1;
        int ans = 0;
        for (int i = 0, j = 0; j < nums.length; ++j) {
            s *= nums[j];
            while (i <= j && s >= k) {
                s /= nums[i++];
            }
            ans += j - i + 1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        long long s = 1;
        int ans = 0, n = nums.size();
        for (int i = 0, j = 0; j < n; ++j) {
            s *= nums[j];
            while (i <= j && s >= k) {
                s /= nums[i++];
            }
            ans += j - i + 1;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func numSubarrayProductLessThanK(nums []int, k int) int {
    s := 1
    ans, i := 0, 0
    for j, x := range nums {
        s *= x
        for i <= j && s >= k {
            s /= nums[i]
            i++
        }
        ans += j - i + 1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function numSubarrayProductLessThanK(nums: number[], k: number): number {
    let s = 1;
    let ans = 0;
    const n = nums.length;
    for (let i = 0, j = 0; j < n; ++j) {
        s *= nums[j];
        while (i <= j && s >= k) {
            s /= nums[i++];
        }
        ans += j - i + 1;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func numSubarrayProductLessThanK(_ nums: [Int], _ k: Int) -> Int {
        if k <= 1 { return 0 }

        var product: Int = 1
        var ans: Int = 0
        var left: Int = 0

        for right in 0..<nums.count {
            product *= nums[right]
            while product >= k {
                product /= nums[left]
                left += 1
            }
            ans += right - left + 1
        }

        return ans
    }
}

评论