題目： LeetCode - 713. Subarray Product Less Than K

題目說明

給一個只含正整數的陣列及整數 k，求陣列中有幾個子陣列相乘的乘積小於 k。

解題思路

由於題目有保證陣列大小會大於 0，所以需要先判斷若 k <= 1 則直接回傳 0，接著使用 Sliding window，遍歷陣列當作確定的右端點 r，左端點 l 從 0 開始，若乘積已經大於等於 k 則將乘積除以 nums[l] 並將 l 加一，此時符合條件的子陣列個數為 r - l + 1。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k)
    {
        if(k <= 1) return 0;
        int l = 0, prod = 1, ret = 0, n = nums.size();
        for(int r = 0; r < n; ++r)
        {
            prod *= nums[r];
            while(prod >= k) prod /= nums[l++];
            ret += r - l + 1;
        }
        return ret;
    }
};