Easy to understand C++ brute force O(n^2)


  • 0
    class Solution {
    public:
        int numSubarrayProductLessThanK(vector<int>& nums, int k) {
            int cnt=0, sz=(int)nums.size();
            for (int i=0; i<sz-1; ++i){
                if (nums[i]>=k) continue;
                ++cnt;
                long prod=nums[i];
                for (int j=i+1; j<sz; ++j){
                    prod*=nums[j];
                    if (prod<k)
                        ++cnt;
                    else
                        break;
                }
            }
            return nums[sz-1] >= k ? cnt : cnt+1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.