713. 乘积小于 K 的子数组

713. 乘积小于 K 的子数组

leetcode 链接

解法一：暴力解法

遍历数组，坐标为 i = 0，乘积为 num = nums[i], 如果 num < k，则 i 向后移一位，num *= nums[i]。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function numSubarrayProductLessThanK(nums, k) {
  let res = 0
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i]
    let j = i
    while (num < k && j < nums.length) {
      res++
      j++
      num *= nums[j]
    }
  }
  return res
}

解法二：滑动窗口

解法链接

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function numSubarrayProductLessThanK(nums, k) {
  const n = nums.length
  let ret = 0
  let prod = 1
  let l = 0
  for (let r = 0; r < n; r++) {
    prod *= nums[r]
    while (r >= l && prod >= k) {
      prod /= nums[l]
      l++
    }
    ret += r - l + 1
  }
  return ret
}