leetcode 713. Subarray Product Less Than K 连续子数组之积小于K + 移动窗口

忘是亡心i 2022-06-03 08:52 53阅读 0赞

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的滑动窗口窗口，用变量left来记录其左边界的位置，右边界i就是当前遍历到的位置。遍历原数组，用prod乘上当前遍历到的数字，然后进行while循环，如果prod大于等于k，则滑动窗口的左边界需要向右移动一位，删除最左边的数字，那么少了一个数字，乘积就会改变，所以用prod除以最左边的数字，然后左边右移一位，即left自增1。当我们确定了窗口的大小后，就可以统计子数组的个数了，就是窗口的大小。

为啥呢，比如\[5 2 6\]这个窗口，k还是100，右边界刚滑到6这个位置，这个窗口的大小就是包含6的子数组乘积小于k的个数，即\[6\], \[2 6\], \[5 2 6\]，正好是3个。所以窗口每次向右增加一个数字，然后左边去掉需要去掉的数字后，窗口的大小就是新的子数组的个数，每次加到结果res中即可

建议和[leetcode 560. Subarray Sum Equals K 动态规划DP子数组求和][leetcode 560. Subarray Sum Equals K _DP] 和 [leetcode 152. Maximum Product Subarray 最大连乘子序列 + DP动态规划][leetcode 152. Maximum Product Subarray _ _ DP] 一起学

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int numSubarrayProductLessThanK(vector<int>& nums, int k) 
        {
            if (k <= 1)
                return 0;
            int count = 0, left = 0 , one = 1;
            for (int right = 0; right < nums.size(); right++)
            {
                one *= nums[right];
                while (one >= k)
                {
                    one /= nums[left];
                    left++;
                }
                count += right - left + 1;
            }
            return count;
        }
    };

[leetcode 560. Subarray Sum Equals K _DP]: http://blog.csdn.net/jackzhang_123/article/details/78832149
[leetcode 152. Maximum Product Subarray _ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78016128