力扣每日一题2022-05-05中等题：乘积小于K的子数组

乘积小于K的子数组

• • 题目描述
  • 思路
  • • 双指针滑动窗口
    • • Python实现
      • Java实现

---

题目描述

乘积小于K的子数组

---

思路 双指针滑动窗口

固定右指针，左指针的个数有多少，则以该右指针为结尾的所有子数组就有多少，计算每种情况的乘积，满足条件的就给计数器+1。

Python实现

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans, left, cur = 0, 0, 1
        for right, num in enumerate(nums):
            cur *= num
            while left <= right and cur >= k:
                cur //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

Java实现

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ans = 0, left = 0, cur = 1;
        for (int right = 0; right < nums.length; right++) {
            cur *= nums[right];
            while (left <= right && cur >= k) {
                cur /= nums[left++];
            }
            ans += right - left + 1;
        }
        return ans;
    }
}