LWC 55：713. Subarray Product Less Than K

LWC 55：713. Subarray Product Less Than K

传送门：713. Subarray Product Less Than K

Problem:

Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

0 < nums.length <= 50000.

0 < nums[i] < 1000.

0 <= k < 10^6.

思路： 尺取法的思想，连续的子数组，且在指定范围k内，所以不可能无限乘下去，采用双指针{lf, rt}，一旦乘积大于等于k，则可以停止后续的搜索，同理一旦超过k，那么lf也需要更新。

更新规则： 比如[10,5]，当rt 搜索到5时，lf 搜索到10时，从5出发的子数组有[10, 5] 和[5]，所以cnt += rt - lf + 1即可。

代码如下：

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int cnt = 0;
        int n = nums.length;

        int p = 1;
        int j = 0;
        for (int i = 0; i < n; ++i) {
            p *= nums[i];
            if (p < k) {
                cnt += i - j + 1;            
            }
            else { // p >= k
                for (; j < n; ){
                    p /= nums[j++];
                    if (p < k) break;
                }
                if (p < k) cnt += i - j + 1;
            }
        }
        return cnt;
    }