[leetcode] 713: subarray with product less than k

Title source

leetcode link ：https://leetcode-cn.com/problems/subarray-product-less-than-k/

 

Their thinking

Define a subarray by sliding the window frame , The product of all elements in the sliding window is

product = e[i] * e[i+1] * e[i+2] * ... * e[j]

among ,i Is the left boundary of the sliding window ,j Is the right boundary of the sliding window ,0 <= i <= n,0 <= j <= n,n Represents the array size .

 

The initial state

Left border of sliding window left = 1, Right border right = 1.

product = e[1], If at this time product < k, The number of qualified subarrays in the sliding window count = 1.

 

In the middle

left = i,right = j - 1

product = e[i] * e[i+1] * ... * e[j-1]

Suppose this time product < k, And the cumulative number of qualified sub arrays has been calculated count = x.

 

Next state

Slide the right edge of the window one unit to the right , At this time, the left and right boundaries of the sliding window are updated to

left = i,right = j

product = e[i] * e[i+1] * ... * e[j-1] * e[j]

If product < k, explain [i, j] Is a sub array that meets the conditions . Sliding window inner ratio [i, j] Subarray length is short , And contains e[j] The subarrays of are all qualified subarrays . therefore , The number of new sub arrays that meet the conditions is calculated to be (j - i + 1) individual , to update count = x + (j - i + 1).

If product >= k, explain [i, j] Not a qualified subarray , Now move the left boundary of the sliding window to the right by one unit , to update left = i + 1, new product = e[i+1] * e[i+2] * ... * e[j]. Continue to investigate [i+1, j] The number of qualified subarrays in the range , And according to the new product Update the left and right boundaries of the sliding window .

 

End state

When the left and right boundaries of the sliding window left = n,right = n when , End of the search .

 

The algorithm code is as follows

int numSubarrayProductLessThanK(int* nums, int numsSize, int k)
{
    int i, left, right;
    int product = 1;
    int res = 0;

    for (left = 0, right = 0; right < numsSize; right++) {
        product *= nums[right];

        for (i = left; i <= right; i++) {
            if (product < k) {
                res += (right - left + 1);
                break;
            } else {
                product /= nums[left];
                left++;
            }
        }
    }

    return res;
}