[713] 乘积小于 K 的子数组

给定一个正整数数组 nums 和整数 k 。

请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入：nums = [10,5,2,6], k = 100

输出：8

解释：8 个乘积小于 100 的子数组分别为：[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。

需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2:

输入：nums = [1,2,3], k = 0

输出：0

这道题难点在于想到复杂度小于 O(n2) 的方法来解。需要用到滑动窗口算法，此时复杂度可以做到 O(n)。

我们知道，如果一个数组中所有元素的乘积都小于 k，那么其所有连续子数组的乘积一定都小于 k。

因此，我们遍历每个元素下标作为右边界，不断缩小左边界，直到乘积满足小于 k。

此时该 left 到 right 的数组中所有连续子数组都小于 k，共有 right - left + 1 个（这是由于滑动窗口区间是左闭右闭的，如果是左闭右开区间的话是 right - left 个）。

如 [1,2,3] 乘积小于 10，则有 [1]、[1,2]、[1,2,3] 的乘积都小于 10，共 3 个。

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k <= 1) return 0;

  let res = 0;
  const len = nums.length;

  let temp = 1;

  let left = 0;
  let right = 0;
  while (right < len) {
    temp *= nums[right];

    while (temp >= k) {
      temp /= nums[left];
      left += 1;
    }
    res += right - left + 1;
    right += 1;
  }

  return res;
}