Medium

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并没有计算在内，因为乘积为 100 不满足题目要求的严格小于。

示例 2：

输入：nums = [1,2,3], k = 0
输出：0

提示：

  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 10^6

解题思路

解题思路

这道题要求找出所有乘积小于 k 的连续子数组的数量。我们可以使用滑动窗口的思想来解决这个问题。

核心思路：

  1. 使用双指针维护一个滑动窗口，窗口内所有元素的乘积小于 k
  2. 当乘积 >= k 时，收缩左边界直到乘积再次小于 k
  3. 对于每个右端点，计算以该点为右端点且乘积小于 k 的子数组个数

关键观察： 当我们固定右端点 right 时，以 right 为右端点的合法子数组数量等于 right - left + 1。这是因为左端点可以是 left, left+1, …, right 中的任意一个。

算法步骤：

  1. 初始化 left = 0, product = 1, count = 0
  2. 遍历数组，right 指针向右移动
  3. 将 nums[right] 乘入 product
  4. 当 product >= k 时，将 nums[left] 从 product 中除去，left 右移
  5. 累加当前窗口大小到结果中

时间复杂度优化： 由于每个元素最多被访问两次（一次加入窗口，一次移出窗口），所以时间复杂度为 O(n)。

注意事项： 当 k <= 1 时，由于所有元素都是正整数，不可能有乘积小于 k 的子数组，直接返回 0。

代码实现

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

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        
        left = 0
        count = 0
        product = 1
        
        for right in range(len(nums)):
            product *= nums[right]
            
            while product >= k:
                product //= nums[left]
                left += 1
            
            count += right - left + 1
        
        return count

public class Solution {
    public int NumSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        
        int left = 0, count = 0;
        int product = 1;
        
        for (int right = 0; right < nums.Length; right++) {
            product *= nums[right];
            
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            
            count += right - left + 1;
        }
        
        return count;
    }
}

var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;
    
    let left = 0, count = 0;
    let product = 1;
    
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        
        while (product >= k) {
            product = Math.floor(product / nums[left]);
            left++;
        }
        
        count += right - left + 1;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问两次，一次被右指针访问，一次被左指针访问
空间复杂度O(1)只使用了常数级别的额外空间

相关题目