LeetCode713 乘积小于K的子数组

发表于 | 分类于 |
字数统计: 239 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/subarray-product-less-than-k/

题意

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

解法

维护一个窗口[l,r]，并记录该窗口内数组的乘积cur的值
如果该窗口内的数组的乘积为cur小于k，先记录以nums[r]结尾的子数组个数，窗口向右扩大r++，并且cur乘nums[r];
每次加上以r作为结尾的连续子数组的个数r-l+1
如果窗口内的数组乘积cur大于k，窗口向左缩小，先除去nums[l]的值，然后再让l++;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int ans = 0, cur = 1, l = 0;
        for (int r = 0; r < nums.size(); r++) {
            cur *= nums[r];
            while(l <= r && cur >= k) {
                cur /= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;
    }
};