0713. Subarray Product Less Than K¶
题目信息¶
- 题号:
0713
- 难度:
Medium
- 主题:
数组、连续子数组、乘积计数
- 原题:
- 重点:
统计的是按起止位置区分的非空连续子数组,乘积必须严格小于
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 的子数组。