C/C++教程

LeetCode 713 Subarray Product Less Than K 滑动窗口

本文主要是介绍LeetCode 713 Subarray Product Less Than K 滑动窗口，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

Solution

滑动窗口的思想。不断增大右端点 \(r\)， 当乘积 \(pd\ge k\) 的时候，缩小左端点 \(l\)，最后得到的区间里面所有的子区间都满足条件: 数量为 \(r-l+1\)

点击查看代码 
class Solution {
private:
    int ans = 0;
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int pd = 1;
        int n = nums.size();
        if(k<=1) return 0;
        int l = 0;
        for(int r = 0;r<n;r++){
            pd*=nums[r];
            
            while(pd>=k && l<=r){
                pd/=nums[l];l++;
            }
            //l--;
            ans+=(r-l+1);
        }
        return ans;
    }
};
这篇关于LeetCode 713 Subarray Product Less Than K 滑动窗口的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航