提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

每日一题(2022-05-05)——乘积小于 K 的子数组

数组 2022 每日 05 小于 乘积
2023-06-13 09:18:38 时间

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
}

提交结果：

相关文章