LCR009.乘积小于K的子数组

链接：LCR009.乘积小于K的子数组
难度：Medium
标签：数组、滑动窗口
简介：请找出该数组内乘积小于 k 的连续的子数组的个数。

题解 1 - cpp

• 编辑时间：2021-12-24
• 执行用时：84ms
• 内存消耗：59.7MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
   public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int n = nums.size(), l = 0, r = 0, num = 1, ans = 0;
        while (l < n && r <= n) {
            while (r < n && num < k) num *= nums[r++];
            ans += r - l - (num >= k ? 1 : 0);
            num /= nums[l++];
        }
        return max(ans, 0);
    }
};

题解 2 - cpp

• 编辑时间：2021-12-24
• 执行用时：49ms
• 内存消耗：59.8MB
• 编程语言：cpp
• 解法介绍：双指针。

class Solution {
   public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int ans = 0, num = 1, l = 0;
        for (int r = 0; r < nums.size(); r++) {
            num *= nums[r];
            while (l <= r && num >= k) num /= nums[l++];
            ans += r - l + 1;
        }
        return ans;
    }
};