题目
给你一个整数数组 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 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
思路
1、暴力求每个符合要求的子数组，会超时。。
2、滑动窗口法：如果一个子串的乘积小于k，那么他的每个子集都小于k，而一个长度为n的数组，他的所有连续子串数量是1+2+…n，但是会和前面的重复。 比如例子中[10, 5, 2, 6]，第一个满足条件的子串是[10]，第二个满足的是[10, 5]，但是第二个数组的子集[10]和前面的已经重复了，因此我们只需要计算包含最右边的数字的子串数量，就不会重复了，也就是在计算[10, 5]这个数组的子串是，只加入[5]和[10, 5]，而不加入[10]，这部分的子串数量刚好是r - l + 1
题解
1、暴力超时法
def numSubarrayProductLessThanK(nums, k): if len(set(nums)) == 1: return len(nums) res = 0 for i in range(len(nums)): use = 1 index = i + 1 if nums[i] < k: res += 1 use *= nums[i] while use < k and index < len(nums): if use * nums[index] < k: res += 1 use *= nums[index] index += 1 else: break return res
滑动窗口优化法
class Solution: def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: if k == 0 or k == 1: return 0 res, temp = 0, 1 left = 0 for right in range(len(nums)): temp *= nums[right] while temp >= k: temp /= nums[left] left += 1 res += right - left + 1 return res
