Java two pointers


  • 0
    C

    Quite similar to what others have already posted. Use two pointers to track a longest sub-array ending at a certain position, which has a product less than k.
    i will be the position right before the start of this sub-array.
    j will be the end of this sub-array.
    then j-i will be the number of desired sub-arrays that end at position j.
    Add all such j-i we have the answer.
    when accumulated product is equal to or larger than k, shrink the array by moving i to the right.

    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            if(k == 0) return 0;
            int res = 0;
            long p = 1;
            for(int i=-1, j=0; j<nums.length; j++) {
                if(nums[j] >= k) {
                    p = 1;
                    i=j;
                } else {
                    p *= nums[j];
                    while(p >= k) {
                        p /= nums[++i];
                    }
                    res += j-i;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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