題目

核心思路

對(duì)于求K相關(guān)的子數(shù)組，一種比較常用的方法是計(jì)算前綴和(積)，然后通過雙指針來做，不過這道題給的數(shù)的范圍最大的積為1000^50000，實(shí)在是太大了，難以實(shí)行，官方題解給出了一種轉(zhuǎn)化為log函數(shù)相加來防溢出，不過不好理解，若想了解還請(qǐng)看官方題解 713-官解點(diǎn)這里 。

下面來講解另一種類似的解法，同樣是雙指針，因?yàn)轭}目給出了數(shù)組元素為正整數(shù)，故當(dāng)前乘積 product 乘以/除以一個(gè)數(shù)是單調(diào)的，可以使用滑動(dòng)窗口來解題。一個(gè)指針left標(biāo)記窗口左端，right標(biāo)記窗口的右端，乘積大于等于K時(shí)，用乘積除以nums[left]，然后使得left向前移；若乘積小于K，計(jì)算 left 到 right 滿足條件的子數(shù)組的個(gè)數(shù)即可。大體思路清楚了，還剩下一點(diǎn)就是求 left 到 right 的子數(shù)組的個(gè)數(shù)待解決，我們通過下圖來理解。

完整代碼

public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1)
            return 0;
        int count = 0;
        int left = 0, right = 0, n = nums.length;
        int product = 1;//存儲(chǔ)當(dāng)前滑動(dòng)窗口的乘積
        for (; right < n; right++) {
            product *= nums[right];
            while (product >= k)
                product /= nums[left++];
            count += right - left + 1;
        }
        return count;
    }

代碼比較簡潔，不過其中的求每個(gè)滑動(dòng)窗口的子數(shù)組個(gè)數(shù)公式 right - left + 1 不是很好發(fā)現(xiàn)，需要仔細(xì)研究。