Leetcode之713-乘积小于k的子数组(Subarray Product Less Than K)

算法题

题干

找出该数组内乘积小于 k 的连续的子数组的个数

示例

1
2
3
4
输入: 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的子数组

说明

  1. 0 < nums.length <= 50000
  2. 0 < nums[i] < 1000
  3. 0 <= k < 10^6

解法

  1. 暴力破解(开始我也仅想出类似的解法)
  2. 双指针+滑动窗口(始终确保滑动窗口的乘积恰好小于k)

解法2思路

  1. 可以肯定的是, 乘积小于k的子数组都是以数组元素为末尾的子数组(貌似是废话)
  2. 维持两个指针i和left
  3. i代表外层for循环的位置, 换句话说为滑动窗口的右边界
  4. left代表滑动窗口的左边界
  5. 我们始终确保滑动窗口里的元素累积结果恰好刚刚小于k, 算上left-1位置的元素肯定会大于等于k
  6. 确定这样的滑动窗口之后, 以滑动窗口末位元素结尾的子数组即当前滑动窗口乘积小于k的子数组
  7. 假设滑动窗口为[1,2,3], 乘积为7, 那么当前滑动窗口子数组为[3]、[2,3]以及[1,2,3]

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length < 1 || k <= 1) {
return 0;
}
int count = 0;
int left = 0;
int multiResult = 1;
final int LENGTH = nums.length;
for (int i = 0; i < LENGTH; i++) {
multiResult *= nums[i];
while (multiResult >= k) {
multiResult /= nums[left++];
}
count += (i - left + 1);
}
return count;
}

代码解析

  1. 第11-13行代码, 用于确定滑动窗口的最左边界
  2. 第14行代码, 累加子数组个数

思考题

  1. 如果数组元素未限定正数这个条件, 本算法题该如何解?
  2. 是否明白代码中i-left+1的含义?
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%