描述

给你一个整数数组 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

提示:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subarray-product-less-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题，我属实有心理阴影….在我刚开始做题的时候…

a

一遍一遍提交，都不通过…提交的次数比这个多，只不过没有显示全【红色的】，绝望的一批 (ノ｀Д)ノ，颇有想掀桌子的冲动，然后今天又碰到这题了，虽然一次通过了，但仍心有余悸…o(≧口≦)o【仍想了挺久的】然后记录一下题解…整理一下思路

思路

首先这个题要求的是乘积,就不能用数组前缀乘积了，因为一直乘积可能会超过int的范围，虽然可以用 长整型long，但不建议这么用。【这是我第一次做题的时候的思路，还是太年轻，因为每次看到数组滑窗，总会想到前缀和】

既然是滑窗，就得定义窗口左右的指针

1
int left = -1,right = 0;

初始化窗口的乘积以及连续子数组的数目

1
2
int mult = nums[0];  //注意，数组的长度是大于等于1的
int result = 0;

  1. 当窗口的乘积<k时

    1. 连续子数组的数目 加上 窗口的大小result+=(right-left);【？为什么加上窗口的大小呢，稍后图示说明，感觉这个应该算是题的一个难点吧】
    2. 然后右边扩大窗口 right++;mult*=nums[right];

  2. 当窗口乘积>=k时

    1. 左边窗口缩小 left++;mult/=nums[left];

      注意，有可能这个左边窗口缩小到left>=right,那就需要扩大右边的窗口了right++;mult*=nums[right];。

      1
      2
      3
      4
      if(left>=right){
          right++;
          mult*=nums[right];
      }

以nums = [10,5,2,6], k = 100为例。

1

result+=1，子数组是[10]

2

result+=2，子数组是[10,5],[5]

3

窗口子数组就没有严格小于k，缩小窗口。

4

result+=2，子数组是[5,2],[2]

5

result+=2，子数组是[5,2,6],[2,6],[6]

由于窗口已经到达边界，所以结束，result=8

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left = -1,right = 0;
        int mult = nums[0];
        int result = 0;
        while (right<nums.length){
            if(mult<k){
                result+=(right-left);
                right++;
                mult*=nums[right];
            }else {
                left++;
                mult/=nums[left];
                if(left>=right){
                    right++;
                    mult*=nums[right];
                }
            }
        }
        return result;
    }
}

但仍然有个问题，你可以把上述代码运行一下，不出意外的话，应该是出意外了。嘿嘿嘿ο(=•ω＜=)ρ⌒☆

java.lang.ArrayIndexOutOfBoundsException数组越界了。在循环过程中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (right<nums.length){
    if(mult<k){
        result+=(right-left);  //假如此时right = nums.length-1
        right++;               //right = nums.length
        mult*=nums[right];      //nums[nums.length]就会越界。
    }else {
        left++;
        if(left>=right){
            right++;
            mult*=nums[right];  //这也同样
        }
        mult/=nums[left];
    }
}

所以需要把mult*=nums[right];，改为if(right<nums.length) mult*=nums[right];。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left = -1,right = 0;
        int mult = nums[0];
        int result = 0;
        while (right<nums.length){
            if(mult<k){
                result+=(right-left);
                right++;
                if(right<nums.length) mult*=nums[right];
            }else {
                left++;
                mult/=nums[left];
                if(left>=right){
                    right++;
                    if(right<nums.length) mult*=nums[right];
                }
            }
        }
        return result;
    }
}

__END__