【python-leetcode713-双指针】乘积小于k的子数组
问题描述: 给定一个正整数数组?nums。 找出该数组内乘积小于?k?的连续的子数组的个数。 示例 1: 输入: nums = [10,5,2,6],k = 100
0 < nums.length <= 50000 ? 解题: 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。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |