本文主要是介绍乘积小于 K 的子数组(LeetCode),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给你一个整数数组
nums
和一个整数k
,请你返回子数组内所有元素的乘积严格小于k
的连续子数组的数目。
解题
"""
时间复杂度:O(n),其中 n 是数组的长度。每个元素最多被访问两次(一次作为右端点,一次作为左端点)。
空间复杂度:O(1),除了输入输出,几乎没有使用额外的空间。
"""def numSubarrayProductLessThanK(nums, k):if k <= 1:return 0prod = 1count = 0left = 0for right in range(len(nums)):prod *= nums[right]while prod >= k and left <= right:prod //= nums[left]left += 1count += right - left + 1return countnums = [10, 5, 2, 6]
k = 100
print(numSubarrayProductLessThanK(nums, k)) # 输出: 8
这篇关于乘积小于 K 的子数组(LeetCode)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!