滑动窗口之乘积小于k的子数组
713. 乘积小于k的子数组
给定一个正整数数组
nums和整数k。 请找出该数组内乘积小于k的连续的子数组的个数。
先敲个黑板
下面一共有两种写法，第一种是按自己理解写的，是过了的，但是 感觉懂了但没完全懂。。。（意思是 我好像懂了滑动窗口 但是写的不规律不条理 好像没完全懂。。）；第二种是更条理的解法，有助于更好的理解~
如果想直接看详细讲解(唠叨)的，可以直接跳过这段代码看下面的分析哦~~~
第一种
第一种就不讲解了哈，可以看完下面的分析来看这段代码，其实也挺好理解的~
/**
* @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这个条件了）
/**
* @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;
};腾讯云开发者
