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

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20009.%20%E4%B9%98%E7%A7%AF%E5%B0%8F%E4%BA%8E%20K%20%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/README.md

剑指 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)$。

Python3

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        i=0
        sm=1 #乘积

        res=0
        for j,x in enumerate(nums):
            sm*=x

            while i<=j and sm>=k:
                sm//=nums[i]
                i+=1
            
            res+=(j-i+1) #连续数组个数=元素个数
        return res

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

TypeScript

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;
}

Swift

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
    }
}