What is the subarray product less than K problem in LeetCode 713?

本文共计397个文字，预计阅读时间需要2分钟。

描述：给定一个正整数数组nums。计算并打印出所有子数组的元素乘积小于k的（连续）子数组数量。

示例1：输入：nums=[10, 5, 2, 6]，k=100输出：子数组数量

Description

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:
Input:

nums = [10, 5, 2, 6], k = 100

Output:

8

Explanation:

The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

• 0 < nums.length <= 50000.
• 0 < nums[i] < 1000.
• 0 <= k < 10^6.

分析

题目的意思是：找出连续子数组数连乘小于K，求满足要求的连续子数组的个数。

• 开始想连乘保存到数组里面，后面会发现，连乘的数会很大，导致溢出。后面选择了这个滑动窗口的方式。

代码

class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k<=1){
return 0;
}
int res=0;
int mul=1;
int left=0;
for(int i=0;i<nums.size();i++){
mul*=nums[i];
while(mul>=k){
mul=mul/nums[left];
left++;
}
res+=i-left+1;
}
return res;
}
};

参考文献

​​[LeetCode] Subarray Product Less Than K 子数组乘积小于K​​