leetcode刷题四十一
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100
输出：8
题目初次解答
这个解答确实是实现了我们所需要的效果，但是超出了时间的限制，运行不能通过。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
res = []
n = 0
l = len(nums)
for i in range(l):
for j in range(i + 1, l + 1):
res.append(nums[i:j])
# print(res)
for a in res:
m = 1
for b in a:
m *= b
if m < k:
n += 1
return
题目解答
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1: return 0
left, right, multi, ans = 0, 0, 1, 0
while right < len(nums):
multi *= nums[right]
while multi >= k:
multi //= nums[left]
left += 1
ans += right - left + 1
right += 1
return
题目运行结果
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
# 使用移动的窗的形式来进行计算，这样可减少计算的次数，也就是可以减少时间上的复杂度。
if k <= 1: return 0
left, right, multi, ans = 0, 0, 1, 0
while right < len(nums):
multi *= nums[right]
# 以右侧元素为pivot
while multi >= k:
# 找到对应这个pivot的最长窗口左侧点
multi //= nums[left]
left += 1
ans += right - left + 1
# 统计以pivot为右侧元素的子数组
right += 1
return
