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 }
提交结果: