Java O(n) solution,Sliding Window


  • 0
    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            int len=nums.length;
            int count=0;
            int prod=1;
            if(k==0)
                return 0;
            for (int left=0,right=-1;left<len;++left)
            {
                while (right+1<len && nums[right+1]<Math.ceil((double)k/prod))
                {
                    prod*=nums[++right];
                }
                int size=right-left+1;
                if(size>0)
                count+=size;
                prod/=nums[left];
            }
            return count;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.