0713. Subarray Product Less Than K

题目信息

题号:

0713

难度:

Medium

主题:

数组、连续子数组、乘积计数

原题:

LeetCode 0713

重点:

统计的是按起止位置区分的非空连续子数组,乘积必须严格小于 k;数组元素均为正整数

题目重述

给定一个正整数数组 nums 和一个非负整数 k,统计其中有多少个非空连续子数组满足:子数组内所有元素的乘积严格小于 k。

连续子数组必须由原数组中一段相邻元素组成;即使两个子数组的值序列相同,只要起止位置不同,也分别计数。等于 k 的乘积不符合条件。数组长度在 [1, 3 * 10^4] 范围内,1 <= nums[i] <= 1000,0 <= k <= 10^6。

自建示例

严格小于边界:

输入:nums = [1,2,4], k = 8
输出:4
解释:符合条件的连续子数组是 [1]、[2]、[4] 和 [1,2]。子数组 [2,4] 与 [1,2,4] 的乘积都等于 8,不满足“严格小于”要求。

阈值不大于一:

输入:nums = [1,1,3], k = 1
输出:0
解释:所有元素都是正整数,任意非空连续子数组的乘积至少为 1,因此没有乘积严格小于 1 的子数组。