【python-leetcode713-双指针】乘积小于k的子数组

概述问题描述： 给定一个正整数数组 nums。 找出该数组内乘积小于 k 的连续的子数组的个数。 示例 1: 输入: nums = [10,5,2,6], k = 100输出

问题描述：

给定一个正整数数组 nums。

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

示例 1:

输入: nums = [10,5,2,6],k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10],[5],[2],[6],[10,5],[5,2],[2,6]。
需要注意的是 [10,2] 并不是乘积小于100的子数组。

说明：:

0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6

 

解题：

class Solution:    def numSubarrayProductLessthanK(self,nums: List[int],k: int) -> int:        #由于nums是由正整数构成，如果k小于等于1，直接返回0        if k<=1:            return 0        用于存储结果        res =从左至右依次遍历数组,i相当于左指针        for i in range(len(nums)):            如果当前值小于k，结果加1            if nums[i]<k :                res+=1            r为右指针                r=i+1            记录当前值            cur=nums[i]            右指针开始遍历            while r<len(nums):                左指针的值先乘以右指针的值                cur=cur*nums[r]                如果当前值小于k，说明这个子数组可以                if cur<k:                    值加1                    res+=1                    右指针右移一位                    r+=1                else:                    否则说明该子数组不行，退出while循环                    break        return res

结果：超出时间限制，也过了74个实例，说明思想是正确的。

为什么超出时间限制，是因为在while循环中计算复杂度太过复杂。

改进之后：

l为左指针            res,l=0,0        用于相乘        tmp = 1        获取右指针right和当前值val        for right,val  enumerate(nums):            先乘以一位            tmp = tmP*val            当前值大于等于k，说明值太大了，最左边的出去，左指针右移一位            while tmp>=k:                tmp=tmp/nums[l]                l+=1            否则的话，当前符合的子数组个数为right-l+1            res+=right-l+1        return res

结果：核心就是res+=right-l+1

不好理解举个例子就知道了，比如说[10,6]。k=100

l=0,r=0,tmp=10，此时数组[10]，结果有0-0+1=1个，也就是它自己

i=0,r=1,tmp=50，此时数组[10,5]，结果有1-0+1=2个，也就是[10,5]和[5]

i=0,r=2,tmp=100，此时数组[10,2]，此时不符合题意了，tmp变为50，l+1=1，子数组为[5,2]，有2-1+1=2个，也就是[5,2]和[2]

i=1,r=3,tmp=60，此时数组为[5,6]，结果有3-1+1=3个，也就是[2]、[6]、[5,6]

所以总共有：1+2+2+3=8个

公式怎么来的呢？

我们可以这么看：正常情况下

[10]：1种，l=0,r=0

[10,5]：3种，重复计算了[10]，剩余2种，l=0，r=1，1-0+1=2

[10,2]：6种，重复计算了[10]、[5]、[10,5]，剩余3种，l=0，r=2，2-0+1=3

[5,2]：3种，重复计算了[5]，剩余2种，i=1，r=2，2-1+1=2

[5,6]：6种，重复计算了[5]、[2]、[5,2]，剩余3种,i=1，r=3，3-1+1=3种

祛除了重复计算的，正好每一轮是r-l+1。

总结

以上是内存溢出为你收集整理的【python-leetcode713-双指针】乘积小于k的子数组全部内容，希望文章能够帮你解决【python-leetcode713-双指针】乘积小于k的子数组所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。