当前位置 博文首页 > 布谷鸟：算法练习：乘积小于K的子数组
给定一个正整数数组 nums。
找出该数组内乘积小于 k 的连续的子数组的个数。
输入: 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的子数组。
说明:
0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6
链接：https://leetcode-cn.com/problems/subarray-product-less-than-k
# 该方法提示超时
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if not nums:
return None
count = 0
length = len(nums)
for i in range(0,length):
if nums[i] < k:
count += 1
j = i + 1
mult = nums[i]
while j < length:
mult *= nums[j]
if mult < k:
count += 1
j += 1
else:
break
return count
我们可以使用二分查找解决这道题目，即对于固定的 i，二分查找出最大的 j 满足 nums[i] 到 nums[j] 的乘积小于 k。但由于乘积可能会非常大（在最坏情况下会达到 1000^50000，会导致数值溢出，因此我们需要对 nums 数组取对数，将乘法转换为加法，即 log?(∏inums[i])=∑ilog? nums[i]，这样就不会出现数值溢出的问题了。
对 nums 中的每个数取对数后，我们存储它的前缀和 prefix，即 prefix[i+1]=∑nums[x]，这样在二分查找时，对于 i 和 j，我们可以用 prefix[j+1]?prefix[i] 得到 nums[i] 到 nums[j] 的乘积的对数。对于固定的 i，当找到最大的满足条件的 j 后，它会包含 j?i+1 个乘积小于 k 的连续子数组。
# 现在提交也是超时
class Solution:
def numSubarrayProductLessThanK(self, nums, k):
if k <= 1: return 0
mult = 1
count = left = 0
for right, val in enumerate(nums):
mult *= val
while mult >= k:
mult /= nums[left]
left += 1
count += right - left + 1
return count
