713. 乘积小于 K 的子数组
题目描述：
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
题解：
方式1（好理解，但是时间复杂度高）：
思路：
subProduct: 用来存放以num[i]开头子集的乘积，subProduct = subProduct * nums[j]与后续元素相乘，如果满足条件，说明当前的子集算一种，继续与nums[j+1]去相乘，直到j==len(nums)-1或者出现不满足；如果不满足，直接进行下一轮循环（因为num里都是是大于0的，所以相乘是递增的，后续再乘也不再满足条件）；
func numSubarrayProductLessThanK(nums []int, k int) int { count := 0 for i := 0; i < len(nums); i++ { subProduct := 1 for j := i; j < len(nums); j++ { subProduct = subProduct * nums[j] if subProduct < k { count++ } else { break } } } return count }
提交结果：
方式2（滑动窗口）：
思路：
数组中的数全部为正数，乘法为非递减，
也就是说一段乘积小于k的子数组中，所有的子数组都满足答案。
left,right: 当前窗口的左右端点
curProduct: 记录当前窗口的乘积
当curProduct>= k 时，我们考虑将左端点left右移，同时消除原来左端点元素 nums[left] 对 curProduct 的贡献,直到 curProduct>= k不再满足，这样我们就可以得到每个右端点 nums[right] 的最远左端点 nums[left]，从而得知以 nums[right]为结尾的合法子数组个数为 rigth - left + 1。
如果不理解right-left+1，见下图，以例1为例子：
func numSubarrayProductLessThanK(nums []int, k int) int { // left,right: 当前窗口的左右端点 // curProduct: 记录当前窗口的乘积 left, right, curProduct := 0, 0, 1 ans := 0 if k <= 1 { return 0 } // 10 5 2 6 for ; right < len(nums); right++ { curProduct *= nums[right] // 当 cur >= k 时，我们考虑将左端点 left 右移， // 同时消除原来左端点元素 nums[left] 对 curProduct 的贡献 for left <= right && curProduct >= k { curProduct /= nums[left] left++ } ans += right - left + 1 } return ans }
提交结果：
