[LeetCode]Subarray Product Less Than K
作者是 在线疯狂 发布于 2017年10月22日 在 LeetCode.

题目描述：

LeetCode 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:

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.

题目大意：

给定数组nums，求其中乘积小于k的连续子数组的个数。

解题思路：

滑动窗口（Sliding Window）

维护滑动窗口，满足窗口内数组的乘积小于k即可。

Python代码：

class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        product = 1
        ll = rr = -1
        ans = 0
        for num in nums:
            rr += 1
            product *= num
            while ll + 1 <= rr and product >= k:
                product /= nums[ll + 1]
                ll += 1
            ans += rr - ll
        return ans

 

本文链接：https://bookshadow.com/weblog/2017/10/22/leetcode-subarray-product-less-than-k/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。