LeetCode 713. Subarray Product Less Than K

题目链接 Subarray Product Less Than K

相关题目 blog 地址

Continuous Subarray Sum

Subarray Sum Equals K

Maximum Product Subarray



题意非常简单,给定一个序列(元素均为正整数),求子数组数量,子数组要求连续且所有元素之积小于 k

思路是遍历这个序列,每到一个点,选出以该点结尾的有多少个连续的子数组的乘积是小于k的即可.如果累积超过了 k,就从左开始除去,直到<k

talk is cheap, show me the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int numSubarrayProductLessThanK(int[] nums, int k) {
int result = 0;
int product = 1;
int i = 0;
for (int j = 0; j < nums.length; j++) {
product *= nums[j];
while (i <= j && product >= k) {
product /= nums[i++];
}
result += (j - i + 1);
}
return result;

}
月月说要给我打赏,就还是放了二维码,😝