713. 乘積小于K的子數(shù)組

問題

給定一個正整數(shù)數(shù)組 。
找出該數(shù)組內(nèi)乘積小于 的連續(xù)的子數(shù)組的個數(shù)。

示例 1:

輸入:
輸出:
解釋: 個乘積小于的子數(shù)組分別為: 。

需要注意的是 并不是乘積小于100的子數(shù)組。

說明:

解法

第一想法是使用雙指針一直乘，當結(jié)果小于時，將指針與指針之間的子數(shù)組數(shù)量加到結(jié)果中。但是難點在于如何排重。
我們會注意到這樣一種規(guī)律：

• 當等于時，其實只有一種子數(shù)組就是
• 與之間的全部子數(shù)組，必然包含所有的與之間的子數(shù)組

此時會發(fā)現(xiàn)，與子數(shù)組的區(qū)別僅在于是否包含元素，而包含全部元素的子數(shù)組數(shù)量為，這個值，就排除了重復的子數(shù)組，對這個數(shù)字進行暫存就可以在循環(huán)結(jié)束后直接得到數(shù)組數(shù)量。

當乘積不滿足條件時，乘積除以指針元素，指針前進，

代碼

java代碼

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // slow為慢指針，mul為slow與fast之間的乘積，result為滿足條件的數(shù)組個數(shù).
        int slow = 0, mul = 1, result = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // fast指針前移，mul計算新的乘積。
            mul *= nums[fast];
            //此時判斷mul是否已經(jīng)大于k了，當大于時，需要除slow元素直到滿足條件為止
            while (mul >= k && slow <= fast) {
                mul /= nums[slow++];
            }
            //這里可能會有疑問需不需要判斷slow與fast的大小，其實這里不需要判斷，前一步如果slow超過fast了，下一輪時，fast會趕上來。而且slow最多比fast多1，兩者相減再加一等于0，符合數(shù)組數(shù)量為0，不用擔心減成負數(shù)
            result += fast - slow + 1;
        }
        return result;
    }
}