每日一题——乘积小于 K 的子数组

简介: 每日一题——乘积小于 K 的子数组

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
}

提交结果:

相关文章
|
6月前
1685. 有序数组中差绝对值之和
1685. 有序数组中差绝对值之和
|
8月前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
8月前
|
存储 测试技术 索引
每日一题——除自身以外数组的乘积
每日一题——除自身以外数组的乘积
|
8月前
|
算法 程序员
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
125 0
|
算法 索引
代码随想录训练营Day2:1.有序数组的平方 2.长度最小的子数组3,螺旋矩阵
代码随想录训练营Day2:1.有序数组的平方 2.长度最小的子数组3,螺旋矩阵
29 0
|
算法
【学会动态规划】乘积为正数的最长子数组长度(21)
【学会动态规划】乘积为正数的最长子数组长度(21)
74 0
力扣 713. 乘积小于 K 的子数组
力扣 713. 乘积小于 K 的子数组
68 0
每日一题——长度最小的子数组
每日一题——长度最小的子数组
|
人工智能 算法
刷题之寻找 3 个数的最大乘积和拼数及四平方和
刷题之寻找 3 个数的最大乘积和拼数及四平方和
144 0
每日一题:Leetcode209 长度最小的子数组
每日一题:Leetcode209 长度最小的子数组