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

本文主要是介绍剑指 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 的子数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！