乘积小于k的子数组

问题描述：给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

说明:
0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6

/**
* 思路：
* 采用滑动窗口的解法：维护一个数字乘积刚好小于k的滑动窗口窗口，
* 用变量l来记录其左边界的位置，右边界r就是当前遍历到的位置。
* 遍历原数组，用product乘上当前遍历到的数字，
* 然后进行while循环，如果product大于等于k，
* 则滑动窗口的左边界需要向右移动一位，删除最左边的数字，那么少了一个数字，乘积就会改变，
* 所以用product除以最左边的数字，然后左边右移一位，即l自增1。
* 当我们确定了窗口的大小后，就可以统计子数组的个数了，就是窗口的大小。

* 为什么子数组的个数就是窗口的大小？
* 比如[5 2 6]这个窗口，k还是100，右边界刚滑到6这个位置，
* 这个窗口的大小就是包含6的子数组乘积小于k的个数，即[6], [2 6], [5 2 6]，正好是3个。
* 所以窗口每次向右增加一个数字，然后左边去掉需要去掉的数字后，
* 窗口的大小就是新的子数组的个数，每次加到结果res中即可。
* 
* 注意：
* 这里要求子集的乘积值必须小于k
*/
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k<=1){
            return 0;
        }

        int l=0;
        int r=0;
        int res=0;
        //[l..r]表示的是乘积和<k的窗口
        int product=1;
        while(r<nums.length){
            product*=nums[r];
            while(product>=k){
                product/=nums[l];
                l++;
            }
            //r-l+1表示的就是[l...r]窗口的长度
            res+=(r-l+1);
            r++;
        }
        return res;
    }
}

参考：

• Java面试宝典
• 编程学习笔记