leetcode 713. 乘積小于K的子數組

題目描述：

給定一個正整數數組 nums。

找出該數組内乘積小于 k 的連續的子數組的個數。

輸入: nums = [10,5,2,6], k = 100

輸出: 8

解釋: 8個乘積小于100的子數組分别為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。

需要注意的是 [10,5,2] 并不是乘積小于100的子數組。

解題步驟：

該題可以采用滑動視窗的方法，如果視窗内乘積大于等于k，則将左指針右移，反之将右指針左移。

該題關鍵在于，如何去确定每次增加的子數組個數。

視窗：[10] 此時增加了 [10]

視窗：[10, 5] 此時增加了 [10,5] — [5]

視窗：[5, 2] 此時增加了 [5, 2] — [2]

視窗：[5,2,6] 此時增加了 [5, 2, 6] — [2, 6] — [6]

根據上面可以看出規律，每次增加的子數組個數，就是目前視窗内的元素個數。

代碼：

public int numSubarrayProductLessThanK(int[] nums, int k) {
    	if(nums.length==0 || k<=1)
    		return 0;
    	int val = 1;
    	int count = 0;
    	int left = 0;
    	for (int i = 0; i < nums.length; i++) {
			val = val*nums[i];
			while(val >= k) {
				val = val/nums[left++];
			}
			count = count + i-left+1;
		}
    	return count;
    }