713. 乘积小于 K 的子数组

713.乘积小于 K 的子数组

题目描述：

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

数据范围：

$1\le nums.len \le 3\times 10^4, 0\le k\le 10^6$

题解：

如果是小于 $k$ ，那么可以直接滑动窗口，维护窗口内的乘积，保证小于 $k$ 。每次加入一个新的数字，调整左窗口，保证乘积小于 $k$ ，然后直接加上以 $r$ 结尾的子数组个数。

如果是等于 $k$ ，可以使用前缀和，维护前缀的乘积，然后使用hash直接查询 $mul / k$ 出现了几次。

当然小于 $k$ 也可以前缀和处理，就是需要二分查出来边界。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int numSubarrayProductLessThanK(vector<int> &nums, int k)
    {
        int l = 0, r = 0;
        int ans = 0;
        long long mul = 1;
        int n = nums.size();
        for (r = 0; r < n; ++r)
        {
            mul *= nums[r];
            while (l <= r && mul >= k)
            {
                mul /= nums[l];
                ++l;
            }
            ans += (r - l + 1);
        }
        return ans;
    }
};