剑指 Offer II 009. 乘积小于 K 的子数组

2021/12/8 23:16:57

本文主要是介绍剑指 Offer II 009. 乘积小于 K 的子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述滑动窗口,注意数组个数的规律。
在这里插入图片描述

如图所示,在left-right中的滑动窗口中,我们需要将以6为边界的所有数组加入计算中,而不是每次计算所有的。

举例:现有ABCD四个数在滑动窗口内,他们的乘积小于k,所以我们要将ABCD、BCD、CD、D四个数组计算在内。

那么问题来了 BC 必然同样也小于k,我们怎么计算呢?

答案是:在之前的滑动窗口中,我们必然已经经过了以C为边界的滑动数组,在这种情况下,所有以C为边界的数组都会被计算在内,根本不需要考虑其他的部分。

想通了上面的道理,接下来就很好办了。

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int left=0;
        int res = 1;
        int count = 0;
        int right = 0;
        while(right<nums.length){
            res = res * nums[right];//到了right位置 把right乘进去
            while(res>=k&&left<right){
                res = res / nums[left];
                left++;//左侧的指针一直向前,直到res合规合法
            }
            if(res<k){
                //res合规的情况下开始计算
                count = count + (right - left + 1);
                //这里有点难以理解 比如说ABCD 我们取以D为界限的所有数组放进去
                //ABCD的乘积小于D 那么ABCD BCD CD D 都是要加进去的 一个四个
                //这时候left = 0 right = 3 所以就是right-left+1
                //那么前面的BC呢?在C作为边界的过程中已经被算进去了!所以不需要。
            }
            right++;
        }
        return count;
    }
}


这篇关于剑指 Offer II 009. 乘积小于 K 的子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程