713. Subarray Product Less Than K

发表于 | 分类于

每日一题 2019 - 01 - 23

题目：

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:

1
2
3
4
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

所以思路就是：我们可以维护一个窗口，通过窗口的滑动来进行判断，比如题中给定的10,5,2,6这个序列

  • 首先窗口大小为 1 ，此时窗口内内容为 10，窗口内元素乘积为 10，所以满足情况
  • 增大窗口长度为 2，此时窗口内内容为10,5，窗口内元素乘积为 50，所以满足情况
  • 继续增大窗口长度为 3，此时窗口内内容为10,5,2,窗口内元素乘积为100，此时就不满足情况，所以此时我们需要将窗口缩短，也即将窗口左边界减一，所以此时窗口长度为 2 ，窗口内内容为5,2,此时又满足情况
  • 继续操作，直到遍历完全所有给定数组所有内容

还要注意一点，就是我们上面求出的序列，并不能满足我们的题意要求，因为我们的题目要求求出所有子序列，那么我们可以这么想，比如10,5这个序列，10,5,10,5,但是10我们已经在第一步中记录过，所以只需要记录后两个记录，所以我们可以使用right - left + 1，也即窗口左边界-窗口右边界的方法，记录满足题意的情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int total = 1;
        int left = 0 ;
        int number = 0 ;
        if(k <= 1)
        {
            return 0;
        }
        for(int right = 0 ; right < nums.size() ; right ++  )
        {
            total *= nums[right];
            while(total >= k )
            {
                total /= nums[left] ;
                left ++ ;
            }
            number += ( right - left + 1 ) ;
        }
        return number ;
    }
};
0%
undefined