713 - Subarray Product Less Than K

解法一 - Two Pointer

下面的實作方法也算是用到 Two Pointer,可是因為每次都需要重新計算 product,在某些 case 下就會 TLE:

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int n=nums.size();

        int count = 0;
        for(int i=0; i<n; i++) {
            int l=i, r=l;

            int product = 1;
            while(r<n) {
                product *= nums[r];

                if(product < k) {
                    count++;
                    r++;
                }
                else if(product >= k) {
                    break;
                }
            }
        }

        return count;
    }
};

解法二 - Two Pointer + Sliding Window

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k <= 1) return 0;
        int n=nums.size();

        int count = 0, product = 1, l = 0;
        for(int r=0; r<n; r++) {
            product *= nums[r];

            while(product >= k) {
                product /= nums[l];
                l++;
            }

            count += r-l+1;
        }

        return count;
    }
};

results matching ""

    No results matching ""