713.乘积小于k的子数组.md

713.乘积小于 k 的子数组

/*
 * @lc app=leetcode.cn id=713 lang=typescript
 *
 * [713] 乘积小于K的子数组
 */

// @lc code=start
function numSubarrayProductLessThanK(nums: number[], k: number): number {}
// @lc code=end

解法 1: 前缀积(超内存)

因为数据会超过最大安全整数,所以需要用 BigInt 去保证结果的正确性,但 BigInt 会随着数字变大所占用的内存也会变大,当数据量太大时,会超出内存的限制

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k === 0 || k === 1) return 0
  const p: bigint[] = [1n]
  for (let [k, v] of nums.entries()) {
    p[k + 1] = p[k] * BigInt(v)
  }

  let res = 0
  for (let i = 1; i < p.length; i++) {
    let l = 0,
      r = i
    let num = p[i] / BigInt(k)
    while (l < r) {
      const mid = (l + r) >> 1
      if (p[mid] > num) {
        r = mid
      } else {
        l = mid + 1
      }
    }

    res += i - l
  }
  return res
}

解法 2: 双指针

整体思路是固定左指针 $i$,然后找到从 $i$ 开始能满足题目条件的最远位置

1. 使用 $p$ 保存当前乘积的结果,固定指针 $i$,每次将指针 $j$ 右移并将 $nums[j]$ 乘 $p$ 的结果保存为 $p$
2. 然后判断 $p$ 是否大于 $k$,当第一次遇到 $p$ 大于 $k$ 的情况时,说明 $i$ 到 $j-1$ 之间的乘积都会小于 $k$,也就是以 $i$ 为子数组的开始位置,以 $i~j-1$ 的每个位置作为结束位置的子数组都满足要求,并且以 $i$ 为开始位置的子数组只有这些数量($j-i$),将当前 $j-i$ 计入答案
3. 接着我们右移 $i$,并将 $p$ 除以 $nums[i]$,并判断 $p$ 是否小于 $k$,如果不小于 $k$,说明以当前这个 $i$ 为开始位置的子数组依然最远只能到 $j-1$ 为止,将的 $j-i$ 计入答案,继续右移 $i$,直到 $p$ 小于 $k$ 为止
4. 之后右移 $j$,重复上述过程

function numSubarrayProductLessThanK(nums: number[], k: number): number {
  if (k === 0 || k === 1) return 0
  let res = 0,
    p: number = 1
  for (let i = 0, j = 0; j <= nums.length; j++) {
    p *= nums[j]
    while (p >= k || (j === nums.length && i < j)) {
      res += j - i
      p /= nums[i++]
    }
  }
  return res
}

Case

test.each([
  { input: { nums: [10, 5, 2, 6], k: 100 }, output: 8 },
  { input: { nums: [1, 2, 3], k: 0 }, output: 0 },
])('input: nums = $input.nums, k = $input.k', ({ input: { nums, k }, output }) => {
  expect(numSubarrayProductLessThanK(nums, k)).toEqual(output)
})