乘积小于 K 的子数组
难度:
标签:
题目描述
代码结果
运行时间: 78 ms, 内存: 18.0 MB
/*
* 思路: 使用Stream API的方式来处理滑动窗口问题。
* 我们仍然使用滑动窗口的思想,但将其转化为流操作。
* 使用range和map来处理数组元素,并计算有效子数组的数量。
*/
import java.util.stream.IntStream;
public class SubarrayProductLessThanKStream {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int[] product = {1};
int[] count = {0};
int[] start = {0};
IntStream.range(0, nums.length).forEach(end -> {
product[0] *= nums[end];
while (product[0] >= k) {
product[0] /= nums[start[0]++];
}
count[0] += end - start[0] + 1;
});
return count[0];
}
}
解释
方法:
这个题解采用了滑动窗口的策略来找出所有乘积小于 k 的子数组。首先,定义一个变量 prod 来存储当前窗口内所有元素的乘积,和一个计数器 count 来统计符合条件的子数组数目。遍历数组 nums,使用一个右指针 right 表示当前窗口的右边界。对于每一个新的 right,将 nums[right] 乘到 prod 上。如果 prod 大于或等于 k,则移动左指针 left 直到 prod 小于 k。每次找到有效的窗口后,可以通过 right-left+1 计算出新添加的子数组数量,因为每扩展一次右边界,就会增加从 left 到 right 的所有连续子数组。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在k小于等于1时直接返回0,这种情况下是否有可能存在其他的有效子数组?
▷🦆
在滑动窗口算法中,为什么选择右指针向右移动时增加元素至prod,而不是左指针向右移动时减少元素?
▷🦆
您提到每次右指针扩展可以通过right-left+1计算新增的子数组数量,能否具体解释一下这种计算方式的逻辑?
▷🦆
如果nums数组中存在0,这种滑动窗口方法怎样处理?是否需要特别的处理逻辑来应对prod为0的情况?
▷相关问题
乘积最大子数组
给你一个整数数组 nums
,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums
的任何前缀或后缀的乘积都 保证 是一个 32-位 整数