LeetCode 713. 乘积小于 K 的子数组

思路

双循环时间超限，考虑滚动数组和双指针。

代码

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n=nums.size();
        int l=0,r=0;//左右指针
        int s=nums[0];
        long long res=0;
        while(l<=r&&r!=n-1){
            while(s<k){
                res+=r-l+1;
                if(r!=n-1){
                    r++;
                    s*=nums[r];
                }else{
                    break;
                }
            }
            if(s>=k){
                while(s>=k){
                    if(l<n){
                        s/=nums[l++];
                        if(s==1&&l<n){
                            r=l;
                            s=nums[r];
                        }
                    }else{
                        break;
                    }
                }
                if(r==n-1&&s<k) res+=r-l+1;
            }
        }
        return res;
    }
};

1. https://leetcode-cn.com/problems/subarray-product-less-than-k/submissions/ ↩