当前位置 博文首页 > 六六先森的博客：leetcode713最乘积小于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 <= 500000 < nums[i] < 10000 <= k < 10^6值得一提的是，这个方法与我微博里求最小和子数组思想十分接近。
最开始我使用的是动态规划。
解法1：
我们初始化一个二维数组（以示例为例）
【【1,1,1,1】，【1,1,1,1】，【1,1,1,1】，【1,1,1,1】】
然后我们让dp是第i-j的乘积，这里我们只用到右上三角的方阵。
递推公式为dp（i，j）=dp（i，j-1）*dp（i+1,j）/dp（i+1，j）
ps：为了防止除0所以初始化为1.
这里很容易依靠双重循环来实现。
但是空间是O(N^2),时间虽然不至于，但依然是k*n。
代码如下：
class Solution:
def numSubarrayProductLessThanK(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n=0
dp=[[1 for x in range(len(nums))] for y in range(len(nums))]
for i in range(len(nums)):
dp[i][i]=nums[i]
if dp[i][i]<k:
n+=1
for j in range(1,len(nums)):
i=0
while i<len(nums) and j<len(nums):
dp[i][j]=dp[i][j-1]*dp[i+1][j]//dp[i+1][j-1]
if dp[i][j]<k:
n+=1
i+=1
j+=1
return n参考别人的双指针法：
解法2：
i，j都指向首元素。
s为乘积，s不断乘以num【j】得到子数组乘积，满足条件小于k时n+=（j-i+1），n是计数器。
首先我们考察这样一个事实。
假设k很大，有1000.
数组为【1,2,3,4,5】
那么任何子数组都是满足的，针对刚才的方法，n=1+2+3+4+5=15
正好对应所有长度的子数组，
但是不满足（乘积过大时将i向前移动并且除以num【i】以减小乘积这样又得到子数组的乘积小于k子数组）。
这样相当于解决了以num【i】开头的子数组满足条件的值，
接下来求以num【i+1】开头的。
代码实现如下。
class Solution:
def numSubarrayProductLessThanK(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n,i=0,0
mul=1
for j in range(len(nums)):
mul*=nums[j]
while mul>=k:
mul//=nums[i]
i+=1
n+=(j-i+1)
return n