1. 題目

給定一個正整數(shù)數(shù)組 nums。

找出該數(shù)組內(nèi)乘積小于 k 的連續(xù)的子數(shù)組的個數(shù)。

示例 1: 輸入: nums = [10,5,2,6], k = 100 輸出: 8 解釋: 8個乘積小于100的子數(shù)組分別為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。 說明: 0 < nums.length <= 50000 0 < nums[i] < 1000 0 <= k < 10^6

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subarray-product-less-than-k
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 滑動窗口，連續(xù)乘積 < k，右端點向右擴(kuò)
• 乘積 >= k，左端點向右收縮

class Solution { //C++ public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if(k == 0)return 0;int i = 0, j = 0, count = 0, product = 1;while(j < nums.size()){if(product*nums[j] < k){ //右端點一直乘product *= nums[j];count += j-i+1;//以j結(jié)尾的子數(shù)組個數(shù)j++;}else// (product*nums[j] >= k){ //乘積大了，左端點移走product /= nums[i++];//有>=k的數(shù)的時候，product可能會變成0if(i > j)j++, product=1;//跳過該數(shù)字}}return count;} };

304 ms 85.3 MB

class Solution:# py3def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:n = len(nums)i, j, count, product = 0, 0, 0, 1while j < n:if product*nums[j] < k:product *= nums[j]count += j-i+1j += 1else:product /= nums[i]i += 1if i > j:j += 1product = 1return count

1512 ms 18 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 713. 乘积小于K的子数组（滑动窗口）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。