leetcode713-- Subarray Product Less Than K

leetcode713-- 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.

这个题目的意思是,给定一个正整数组,返回连续的子数组的积小于K的个数。

首先要明白,如果一个连续子数组的积小于K的话,那么其子数组也是小于K的,

基于此,可以采用双指针的办法,双指针里面的子数组就是刚好小于K时的数组的左右下标,

左边的指针是left, 右边的指针是当前走到的位置i, 每一次更新完这个新的子数组的时候,子数组的长度就是新增的满足条件的个数,因为前面的数组在前面的时候已经被计数了,所以新增的并且以这个指针右边为结束的,刚好就是这个数组的长度,比如[5,2,6]就是[6], [2,6], [5,2,6]

如下


class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        if k<=1:
            return 0
        
        res = 0
        prod = 1
        left = 0
        
        for i in range(len(nums)):
            prod *= nums[i]
            
            while prod>=k:   # 当prod>=k的时候就去掉最左边的那个,同时左边的指针右移.
                prod /= nums[left]
                left += 1
            # 当结束的时候说明当前的prod刚好是小于K的时候。就统计个数
            res += i-left+1
            
        return res

解释

在上面的代码中, 第一个指针相当于是left, 第二个指针相当于是i, 当这之间的prod如果大于等于k的时候就暂时停下来,然后从左边开始去元素,直到最后去的prod刚好小于k的时候终止,这时候这之间的子数组的个数总共有i-left+1 个(以left为开头的).

有个题目是求和小于k, 不过本质上是一样的类型的.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦