給定一個(gè)正整數(shù)數(shù)組?nums和整數(shù) k 。請(qǐng)找出該數(shù)組內(nèi)乘積小于?k?的連續(xù)的子數(shù)組的個(gè)數(shù)。示例 1:輸入: nums = [10,5,2,6], k = 100 輸出: 8 解釋: 8個(gè)乘積小于100的子數(shù)組分別為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。 示例 2:輸入: nums = [1,2,3], k = 0 輸出: 0思路 步驟 1: 當(dāng) left <= right 且滑動(dòng)窗口內(nèi)的乘積小于 k 時(shí)，我們可以知道 [left,right]、[left+1,right]...[right-1,right] 均滿足條件，因此，計(jì)數(shù)加 right-left+1，然后移動(dòng)右 邊界(滑動(dòng)區(qū)間加大)，看剩下的區(qū)間是否滿足乘積小于 k，如果小于 k，重復(fù)步驟 1，否則進(jìn)行步驟2。步驟 2:當(dāng)滑動(dòng)窗口內(nèi)的乘積大于等于 k 時(shí)，右移左邊界(滑動(dòng)區(qū)間減小)，如果 這個(gè)區(qū)間內(nèi)乘積小于 k，進(jìn)入步驟 1，否則重復(fù)步驟 2。class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:left, product, count = 0, 1, 0for right in range(len(nums)):# 右邊界右移product = product * nums[right]# 乘積>=k, 左邊界右移while left <= right and product >= k:product /= nums[left]left += 1# 當(dāng)前右邊界下，滿足條件的數(shù)組count += right - left + 1return count

總結(jié)

以上是生活随笔為你收集整理的11. Leetcode 713. 乘积小于K的子数组 (数组-同向双指针-滑动窗口)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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