713.乘积小于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

//暴力法 很慢
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null || nums.length < 1 || k <= 1) {
            return 0;
        }
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = i; j < nums.length; j++) {
                if(nums[i] < k && isLessThanK(nums, i, j, k)) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }
    
    public boolean isLessThanK(int[] nums,int start, int end, int k) {
        int tmp = 1;
        for(int i = start; i <= end; i++) {
            tmp *= nums[i];
            if(tmp >= k) {
                return false;
            }
        }
        return true;
            
    }
}

双指针+滑动窗口(始终确保滑动窗口的乘积恰好小于k)
可以肯定的是, 乘积小于k的子数组都是以数组元素为末尾的子数组(貌似是废话)
维持两个指针i和left
i代表外层for循环的位置, 换句话说为滑动窗口的右边界
left代表滑动窗口的左边界
我们始终确保滑动窗口里的元素累积结果恰好刚刚小于k, 算上left-1位置的元素肯定会大于等于k
确定这样的滑动窗口之后, 以滑动窗口末位元素结尾的子数组即当前滑动窗口乘积小于k的子数组
假设滑动窗口为[1,2,3], 乘积为7, 那么当前滑动窗口子数组为[3]、[2,3]以及[1,2,3]

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null || nums.length < 1 || k <= 1) {
            return 0;
        }
        int count = 0;
        int multi = 1;
        int left = 0;
        for(int i = 0; i < nums.length; i++) {
            multi *= nums[i];
            while(multi >= k) {
                multi /= nums[left++];
            }
            count += i - left + 1;
        }
        return count;
    }
  
}

链接：https://www.jianshu.com/p/c71ef9c77ea9