> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/shu-zu/713-cheng-ji-xiao-yukde-zi-shu-zu.md).

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

## 题目描述

[713. 乘积小于K的子数组](https://leetcode-cn.com/problems/subarray-product-less-than-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的子数组](/garnet/suan-fa/shu-zu/560-he-weikde-zi-shu-zu.md)中的方法, 使用**前缀和**解题. 连乘经过$$\log$$的转换, 就转换成了连加. 而且由于题目中数组的长度和每个元素的大小情况, 很容易出现溢出的情况, 而$$\log$$转换也解决了这个问题.

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

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

```python
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$$ 的连续子数组。

```python
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
```