713. 乘积小于 K 的子数组

713. 乘积小于 K 的子数组

leetcode 链接

解法一：暴力解法

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

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

解法二：滑动窗口

解法链接

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function (nums, k) {
  let n = nums.length,
    ret = 0;
  let prod = 1,
    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;
};