###### tags: `Leetcode` `medium` `sliding window` `python` `c++`

# 713. Subarray Product Less Than K

## [題目連結:] https://leetcode.com/problems/subarray-product-less-than-k/

## 題目:
Given an array of integers ```nums``` and an integer ```k```, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than ```k```.

**Example 1:**

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.

**Example 2:**

Input: nums = [1,2,3], k = 0
Output: 0

## 解題想法:
* 此題為找出數組中，所有乘積嚴格小於k的**連續子數組**
* **子數組為連續的**
* 子序列可以不連續

* Use Siding Window
* 初始所需:
* 兩pointer做為滑動窗口的左右邊界 (head=0, tail=0 )
* pro=1: 紀錄當前乘積
* res=0: 紀錄總數
* while tail<len(nums):
* Step1: pro累乘nums[tail]
* Step2: 處理不合理範圍，將head右移
* while pro>=k and head<=tail:
* Step3: 累加結果並將tail右移

* Slide window模板技巧介紹[https://blog.csdn.net/fuxuemingzhu/article/details/83047699]

## Python:

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        #slide window O(N) N:len(nums)
        head=0
        tail=0
        pro=1 #目前乘積 
        res=0 #總數
        while tail<len(nums):
            pro*=nums[tail]
            while pro>=k and head<=tail:
                pro/=nums[head]
                head+=1
            res+= tail-head+1
            tail+=1
        return res

result=Solution()
ans=result.numSubarrayProductLessThanK(nums = [10,5,2,6], k = 100)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int head=0, tail=0, pro=1, res=0, n=nums.size();
        while (tail<n){
            pro*=nums[tail];
            while (pro>=k && head<=tail){
                pro/=nums[head];
                head+=1;
            }
            res+=(tail-head+1);
            tail+=1;
        }
        return res;
    }
};