[713][中等][二分][双指针] 乘积小于K的子数组

题目描述

713. 乘积小于K的子数组

给定一个正整数数组 nums。

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

示例 1:

输入: 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的子数组。

说明:

• 0 < nums.length <= 50000

• 0 < nums[i] < 1000

• 0 <= k < 10^6

解题思路

前缀和 + 二分

可以参考[560][中等][前缀和][哈希] 和为K的子数组中的方法, 使用前缀和解题. 连乘经过$\log$的转换, 就转换成了连加. 而且由于题目中数组的长度和每个元素的大小情况, 很容易出现溢出的情况, 而$\log$转换也解决了这个问题.

先对原数组中的每个数字进行对数转换, 然后求得完整的前缀和数组, 然后求每个区间所有元素的连乘结果, 就是前缀数组对应位置之差, 这点与560题中一样. 不一样的是, 560题中只需要找到前缀和为差值为k的前缀位置, 所以可以用哈希边遍历, 边存储, 边判断. 但本题是要找到所有小于k的子数组, 看起来还是要对每个位置再遍历其开头(或结尾)的所有子数组, 一个个进行判别, 但前缀和数组的递增的特殊性质, 让我们可以用二分的方法进行优化.

对于每个位置$i$, 假设我们要遍历以这个数字作为开头的子数组, 是否满足连乘小于$k$, 我们可以对前缀和数组从$i + 1$的位置开始, 寻找$pre[i] + k$值所处的位置, 小于这个数字的位置, 代表的从$i$(包含)到这个位置组成的子数组, 其连乘结果肯定是小于k的, 因此如果我们用二分数组在前缀和数组上找到的位置为$j$, 则以$i$位置开头的子数组满足要求的数量为$j - i - 1$.

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k == 0:
            return 0
        k = math.log(k)

        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1] + math.log(num))

        ans = 0
        for i in range(len(nums)):
            j = bisect.bisect(prefix, prefix[i] + k - 1e-9, lo=i + 1)  # 减去1e-9是消除精度偏差带来的相同数字比较误差
            ans += j - i - 1
        return ans

双指针

对于每个$\mathrm{right}$, 我们要找到满足条件的最小的$\mathrm{left}$.满足 $\prod_{i=\mathrm{left}}^\mathrm{right} \mathrm{nums}[i] < k$. 对于更靠右的$\mathrm{right}$, 其对应的最小的$\mathrm{left}$, 不可能小于靠左的$\mathrm{right}$对应的$\mathrm{left}$. 因此可以使用双指针, 移动右指针的同时, 不断调整左指针的位置.

我们使用一重循环枚举 $\mathrm{right}$，同时设置 $\mathrm{left}$ 的初始值为 0。在循环的每一步中，表示 $\mathrm{right}$ 向右移动了一位，将乘积乘以 $\mathrm{nums}[\mathrm{right}]$。此时我们需要向右移动 $\mathrm{left}$，直到满足乘积小于 $k$ 的条件。在每次移动时，需要将乘积除以 $\mathrm{nums}[\mathrm{left}]$。当 $\mathrm{left}$ 移动完成后，对于当前的 $\mathrm{right}$，就包含了 $\mathrm{right} - \mathrm{left} + 1$ 个乘积小于 $k$ 的连续子数组。

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        left, right, mul = 0, 0, 1
        ans = 0
        while right < len(nums):
            mul *= nums[right]
            while mul >= k:
                mul /= nums[left]
                left += 1
            ans += right - left + 1
            right += 1
        return ans