713. 乘积小于k的子数组

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

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

先敲个黑板

下面一共有两种写法，第一种是按自己理解写的，是过了的，但是 感觉懂了但没完全懂。。。（意思是 我好像懂了滑动窗口 但是写的不规律不条理 好像没完全懂。。）；第二种是更条理的解法，有助于更好的理解~

如果想直接看详细讲解(唠叨)的，可以直接跳过这段代码看下面的分析哦~~~

第一种

第一种就不讲解了哈，可以看完下面的分析来看这段代码，其实也挺好理解的~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    let l=0,r=0;
    let n=nums.length;
    let ans=0;
    let tem=1;
    while(r<n){
        if(l===r){
            if(nums[l]<k){
                ans++;
                r++;
                tem=nums[l]*nums[r];
            }else{
                l++,r++;
            }
        }else{
            while(tem<k && r<n){
                ans=ans+r-l+1;
                r++;
                tem=tem*nums[r];
            }
            l++;
            tem=tem/(nums[l-1]);
        }
    }
    return ans;
};

第二种

首先解释一下，下面的n是指数组长度，k是指乘积需要小于的那个数，ans是指要求解的子数组的个数，l、r是指左右指针。下面的分析比较侧重于推敲思路，可能言语上会有不严谨的地方，大家就当作参考咯（逃！

这种解法同样是 刚开始左右指针指在同一个地方，然后由于乘积小于k，r可以向右移动，乘积继续变化，直到乘积大于等于k，我们就需要进行一些操作了。

我们可以想一想，只要r小于n，那当r每次增加1的时候，我们就可以计算ans，将ans+r-l+1，诶，为什么是r-l+1呢？ 因为我们计算的是连续的子数组的个数，每次右指针移动、加入一个新的右边的数值的时候，在满足l到r的乘积小于k的前提下，总的ans的增加量就是新的值、新的值与之前所有可连续的值的组合，这个就用到一点点数学知识了~

那计算ans的时候l难道一直是1吗？ 不，l是会变化的（排除极端情况），那l什么时候变呢？ l变了之后ans又会是多少呢？

让我们来想一想，我们需要满足的条件是连续数组内的数乘积小于k，当右指针一直向右移动使得乘积不断增大时，总会有大于等于k的时候，那个时候，我们就需要改变l了，在这种情况下，我们计算的ans就不是现在的r-l+1了，因为r指向的值不满足条件，我们需要在改变l之后再去求ans。

那l会发生什么样的改变呀，l会向右移动多少呢？

因为当l不变、r向右移动时，我们的乘积一直都是非递减的，如果当前右指针移动到的位置使得l到r不满足乘积小于k，那我们再继续移动右指针，乘积一定依旧不满足小于k，那就说明这个l我们已经“利用”完了，l可以退出滑动窗口了~

所以l的改变就取决于乘积除以要移除的nums[l]的结果，直到这个结果小于k时，l就不需要再变化了

这个时候我们就能求取当前的l到r对应的ans值了（因为已经满足乘积小于k这个条件了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    if(k===0||k===1){return 0}
    let l=0,r=0;
    let n=nums.length;
    let ans=0;
    let tem=1;
    while(r<n){
        tem=tem*nums[r];

        while(tem>=k){
            tem=tem/(nums[l]);
            l++;
        }

        ans=ans+r-l+1;
        r++;
    }
    return ans;
};