> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/713.-subarray-product-less-than-k.md).

# 713. Subarray Product Less Than K

Your are given an array of positive integers `nums`.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than `k`.

**Example 1:**<br>

```
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
```

**Note:**

`0 < nums.length <= 50000`.

`0 < nums[i] < 1000`.

`0 <= k < 10^6`.

{% hint style="info" %}
利用sliding window的頭尾兩個pointers去找到一個符合條件的最大乘積的區間，每次找到一個新的j pointer就代表可以多形成(j - i + 1)個以nums\[j]結尾的subarrays。
{% endhint %}

```cpp
// Sliding Window
int numSubarrayProductLessThanK(vector<int>& nums, int k) { // time: O(n); space: O(1)
    int res = 0, n = nums.size(), pro = 1;
    for (int i = 0, j = 0; j < n; ++j) {
        pro *= nums[j];
        while (i <= j && pro >= k) {
            pro /= nums[i++];
        }
        res += (j - i + 1); // number of subarrays ending with nums[j]
    }
    return res;
}
```