713 乘积小于K的子数组（枚举技巧、双指针）

刺骨的言语ヽ痛彻心扉 2022-09-07 00:58 113阅读 0赞

**1. 问题描述：**

给定一个正整数数组 nums和整数 k 。请找出该数组内乘积小于 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的子数组。

**示例 2:**

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

**提示:**

1 <= nums.length <= 3 \* 10 ^ 4  
1 <= nums\[i\] <= 1000  
0 <= k <= 10 ^ 6  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/subarray-product-less-than-k

**2. 思路分析：**

分析题目可以知道我们需要先考虑如何**枚举**才能够将所有答案枚举出来，一般考虑以位置i结尾的...，对于这道题目来说我们可以考虑所有以i结尾的数字满足要求的连续子数组的个数，并且我们在枚举当前位置i的时候可以结合**双指针算法**来解决（所有数都是正整数），声明两个指针i，j，当指针i往右走并且乘积大于k之后那么指针j是往右走的所以可以使用双指针算法，i - j + 1就是以当前位置i结尾的满足要求的连续子数组的个数。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 双指针
        def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
            j = 0
            p = 1
            res = 0
            for i in range(len(nums)):
                p *= nums[i]
                while j <= i and p >= k:
                    p //= nums[j]
                    j += 1
                # i - j + 1就是以位置i结尾的满足要求的连续子数组的个数
                res += i - j + 1
            return res