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;
};