题目描述:
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
本文链接:http://bookshadow.com/weblog/2017/10/22/leetcode-subarray-product-less-than-k/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。