# 0713. Subarray Product Less Than K
###### tags: `Leetcode` `Medium` `Prefix Sum` `Sliding Window` `Binary Search`
Link: https://leetcode.com/problems/subarray-product-less-than-k/
## 思路
**这两种方法的前提条件都是所有数都是positive number**
### 思路一 Prefix Sum O(NlogN) O(N) N为nums长度
由于这里是乘法不同于之前加法，乘法可能会导致overflow，所以直接**用log的形式**算
因为要找乘积小于K的，而不是刚好等于K的，所以要用binary search
### 思路二 Sliding Window O(N) O(N)
用这个方法也必须满足所有数都是positive number
ex. [10,5,-2,6] k = 10 当right指针指到-2的时候，left指针指到5，但其实10*(-2）也小于k，但left指针只能往右移动，不能往左移动
## Code
### 思路一

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k == 0) return 0;
        double logk = Math.log(k);
        double[] prefix = new double[nums.length+1];
        for(int i = 0;i < nums.length;i++){
            prefix[i+1] = prefix[i]+Math.log(nums[i]);
        }
        
        int ans = 0;
        for(int i = 0;i < prefix.length;i++){
            int lo = i+1, hi = prefix.length;
            while(lo<hi){
                int mi = lo+(hi-lo)/2;
                if(prefix[mi] < prefix[i]+logk){
                    lo = mi+1;
                }
                else{
                    hi = mi;
                }
            }
            ans+=lo-i-1;
        }
        return ans;
    }
}

### 思路二

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k==0 || k==1) return 0;
        int ans = 0;
        int l = 0, r = 0;
        int prod = 1;
        while(r < nums.length){
            prod *= nums[r];
            while(l<=r && prod>=k){
                prod /= nums[l++];
            }
            ans += r-l+1;
            r++;
        }
        return ans;
    }
}