713. 乘积小于K的子数组

给定一个正整数数组 nums。
找出该数组内乘积小于 k 的连续的子数组的个数。
输入: 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的子数组。

  • 时间复杂度：O(n)，其中 n 是 nums 数组的长度。循环的时间复杂度为O(n)，而 eft 最多移动 n 次，因此总的时间复杂度为 O(n)。

  • 空间复杂度：O(1)。

    1. //滑动窗口法，定住右指针，左指针向他靠拢，<k就是目标数组；但为了去重，只取包含最右数字的组合 r-l+1
    2. //复杂度为啥不是N^2，因为是整体移动，左边指针不需要移动到底，只是在右边的基础上。
    3. func numSubarrayProductLessThanK(nums []int, k int) int {
    4.   if k <= 1 {
    5.       return 0
    6.   }
    8.   left, right := 0, 0
    9.   sum := 1
    10.   res := 0
    12.   for right < len(nums) {
    13.       sum = sum * nums[right]
    14.   //for right, value := range nums {
    15.   //    sum *= value
    17.       for left < right && sum >= k {
    18.           sum = sum / nums[left]
    19.           left++
    20.       }
    22.       res += right - left + 1
    23.       right++
    24.   }
    25.   return res
    26. }
    //暴力法
func numSubarrayProductLessThanK(nums []int, k int) int {
  l := len(nums)

  preAcc := make([]int, l+1)
  preAcc[0] = 1
  for i := 0;i <l;i++ {
      preAcc[i+1] = preAcc[i] * nums[i]
  }
  var result int
  for i := 1; i <= l;i ++ {
      for j := 0; j < i;j++ {
          if preAcc[i] / preAcc[j] < k {      //数组太大，会溢出
              result++
          }
      }
  }
  return result
}