713.乘积小于K的子数组

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

题解 1 - cpp

• 编辑时间：2022-05-05
• 执行用时：76ms
• 内存消耗：9.4MB
• 编程语言：cpp
• 解法介绍：滑动窗口。

int numSubarrayProductLessThanK(int *nums, int numsSize, int k) {
    int l = 0, r = 0, sum = 1, ans = 0;
    while (l < numsSize) {
        while (r < numsSize && sum * nums[r] < k) sum *= nums[r++];
        if (l == r) {
            l++;
            r++;
        } else {
            ans += r - l;
            sum /= nums[l++];
        }
    }
    return ans;
}

题解 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;
    }
};

题解 3 - cpp

• 编辑时间：2021-12-24
• 执行用时：72ms
• 内存消耗：59.8MB
• 编程语言：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);
    }
};