题目描述

乘积小于 K 的子数组
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:

  1. 输入: nums = [10,5,2,6], k = 100
  2. 输出: 8
  3. 解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
  4. 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

  1. 输入: nums = [1,2,3], k = 0
  2. 输出: 0

提示:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106】

    解题思路

  1. 暴力解

双重for循环寻找满足条件的子数组

  1. 动态规划，滑动窗口

image.png
在暴力双循环的基础上，在Pn+1处得到Product>=100，在下一轮循环中，以Pm+1为首元素的众多子数组Pm+1…Pn都一定满足条件，则j可以直接以Pn+1为起点，而不用与i同起点。
滑动窗口——详细题解

实现代码

  1. public int numSubarrayProductLessThanK(int[] nums, int k) {
  2.   int n = nums.length;
  3.   // 乘积
  4.   int product = 1;
  5.   int left = 0, right = 0;
  6.   int count = 0;
  7.   for(;right<n;right++){
  8.     //            当 product<k 扩展右边界
  9.     product *= nums[right];
  10.     //当 product>= k, 收缩左边界
  11.     while(left<=right&&product>=k){
  12.       product /= nums[left++];
  13.     }
  14.     count += right-left+1;
  15.   }
  16.   return count;
  17. }

时间及空间复杂度分析

暴力解时间O(n2)
image.png
滑动窗口时间复杂度O(n)
image.png