【week8】713. Subarray Product Less Than K

713. Subarray Product Less Than K

题目

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Note:

• 0 < nums.length <= 50000.

• 0 < nums[i] < 1000.

• 0 <= k < 10^6.

解题报告

题意很简单，找出满足乘积小于 k 的子数组的数目。

题目提示是使用双指针，我就先搞了个 i，j 作为子数组的头尾，可以很容易想到，如果 $product(i,j)<k$，则 $product(i+1,j)<k$ ，进一步地，假设 $count(i，j)$ 表示以 i 为起始直到 j 的满足条件的子数组数目，则 $count(i+1,j)=count(i,j)-1$，根据这个思路，我完成了 Solution 的大体逻辑。

主要思想是，使用 i 遍历数组，每次找到 j，满足 $product(i,j)\ge k$，求得 $count(i,j)=j-i$， 如果 j == i，则说明 nums[i] >= k，此时将 j 加一，然后 ++i。

时间复杂度为 $O(n)$。

社区有耗时更短的方法，思想似乎和我差不多，不过我是 $j=j+1\ until\ product(i,j)\ge k$，社区的方法是 $i=i+1\ until\ product(i,j)<k$。看上去差不多，不过运算次数快少了一半（我每次需要两次乘运算，而那个解法只需要一次除运算），我尝试简化自己的答案，不过没找到什么可以优化的地方。

Solution

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (!k) return 0;
        int product = 1, count = 0;
        for (int i = 0, j = 0; i < nums.size(); ++i) {
            while (j < nums.size()) {
                if (product * nums[j] < k) {
                    product *= nums[j];
                    ++j;
                } else {
                    break;
                }
            }
            count += j - i;
            if (i != j) product /= nums[i];
            else ++j;
        }
        return count;
    }
};

// others' solution
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k == 0) return 0;
        int cnt = 0;
        int pro = 1;
        for (int i = 0, j = 0; j < nums.size(); j++) {
            pro *= nums[j];
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            cnt += j - i + 1;
        }
        return cnt;
    }
};