leetcode
leetcode 601 ~ 650
乘积小于 K 的子数组

乘积小于 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,这种情况下是否有可能存在其他的有效子数组?
当k小于等于1时,无论数组中的元素如何,任何非空子数组的乘积都至少为1(因为数组元素都是正整数)。因此,不能存在乘积小于1的子数组,所以直接返回0是合理的。
🦆
在滑动窗口算法中,为什么选择右指针向右移动时增加元素至prod,而不是左指针向右移动时减少元素?
滑动窗口的目标是探索所有可能的子数组,而右指针向右移动时增加元素至prod,可以帮助我们持续扩展当前的窗口,从而发现新的符合条件的子数组。如果仅在左指针移动时更新prod,我们将无法有效地利用之前的计算结果,因每次右指针扩展都可能产生新的符合条件的子数组。
🦆
您提到每次右指针扩展可以通过right-left+1计算新增的子数组数量,能否具体解释一下这种计算方式的逻辑?
每当右指针right向右移动并包含一个新元素时,我们可以形成新的子数组,这些子数组的结束点都是新的right位置,起始点从left到right。例如,如果left为2而right为5,那么新增的子数组包括[2,5]、[3,5]、[4,5]和[5]共(right-left+1)个。这样计算可以快速统计每扩展一次右边界时新增的子数组数量。
🦆
如果nums数组中存在0,这种滑动窗口方法怎样处理?是否需要特别的处理逻辑来应对prod为0的情况?
如果数组中存在0,那么任何包含0的子数组的乘积都将是0,这显然小于k(假设k>1)。在遇到0的情况下,prod会变成0,我们需要重置prod为1并将左指针移动到0的下一个位置,因为包含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-位 整数

和等于 k 的最长子数组长度

和等于 k 的最长子数组长度

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

子数组是数组中元素的连续非空序列。

 

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

小于 K 的两数之和

小于 K 的两数之和