[LeetCode] 713. Subarray Product Less Than K

轉自LeetCode

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.

<Solution>

想法如下

• 用兩個指標，紀錄目前 subarray 的左邊界和右邊界。如果目前的乘積依然小於 k，那麼右邊界繼續向右動，左邊界不動；若是乘積大於等於 k，那麼將左邊界往右移，並且將乘積除掉剛剛左移的數字

• 而每次能增加的 subbarray 數目，等於 right - left + 1

code 如下

Java(參考解答)

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

view raw numSubarrayProductLessThanK.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
	return if (k <= 1) {
	0
	} else {
	var ans = 0
	var left = 0
	var product = 1
	for(right in nums.indices) {
	product *= nums[right]
	while(product >= k) {
	product /= nums[left++]
	}
	ans += right - left + 1
	}
	ans
	}
	}
	}

view raw subarray_product_less_than_k.kt hosted with ❤ by GitHub