713. 乘積小于K的子數(shù)組
問(wèn)題
給定一個(gè)正整數(shù)數(shù)組 。
找出該數(shù)組內(nèi)乘積小于 的連續(xù)的子數(shù)組的個(gè)數(shù)好啰。
示例 1:
輸入:
輸出:
解釋:個(gè)乘積小于
的子數(shù)組分別為:
。
需要注意的是 并不是乘積小于100的子數(shù)組儿奶。
說(shuō)明:
解法
第一想法是使用雙指針一直乘框往，當(dāng)結(jié)果小于時(shí)，將
指針與
指針之間的子數(shù)組數(shù)量加到結(jié)果
中闯捎。但是難點(diǎn)在于如何排重椰弊。
我們會(huì)注意到這樣一種規(guī)律：
- 當(dāng)
等于
時(shí)许溅，其實(shí)只有一種子數(shù)組就是
-
與
此時(shí)會(huì)發(fā)現(xiàn)秉版，與
子數(shù)組的區(qū)別僅在于是否包含
元素贤重，而包含全部
元素的子數(shù)組數(shù)量為
，這個(gè)值清焕，就排除了重復(fù)的子數(shù)組并蝗，
對(duì)這個(gè)數(shù)字進(jìn)行暫存就可以在循環(huán)結(jié)束后直接得到數(shù)組數(shù)量。
當(dāng)乘積不滿(mǎn)足條件時(shí)秸妥，乘積除以指針元素滚停，
指針前進(jìn)，
代碼
java代碼
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
// slow為慢指針粥惧，mul為slow與fast之間的乘積键畴，result為滿(mǎn)足條件的數(shù)組個(gè)數(shù).
int slow = 0, mul = 1, result = 0;
for (int fast = 0; fast < nums.length; fast++) {
// fast指針前移，mul計(jì)算新的乘積突雪。
mul *= nums[fast];
//此時(shí)判斷mul是否已經(jīng)大于k了镰吵，當(dāng)大于時(shí)，需要除slow元素直到滿(mǎn)足條件為止
while (mul >= k && slow <= fast) {
mul /= nums[slow++];
}
//這里可能會(huì)有疑問(wèn)需不需要判斷slow與fast的大小挂签，其實(shí)這里不需要判斷疤祭，前一步如果slow超過(guò)fast了，下一輪時(shí)饵婆，fast會(huì)趕上來(lái)勺馆。而且slow最多比f(wàn)ast多1，兩者相減再加一等于0侨核，符合數(shù)組數(shù)量為0草穆，不用擔(dān)心減成負(fù)數(shù)
result += fast - slow + 1;
}
return result;
}
}
