LeetCode LCR 009. 乘积小于 K 的子数组

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ LCR 009. 乘积小于 K 的子数组

思路分析

解法一：滑动窗口（推荐）

核心思路：

维护窗口内乘积，右指针扩展时更新乘积。

若乘积不小于 k，则移动左指针缩小窗口。

每个右端点贡献的有效子数组数量为 right - left + 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }

        int left = 0;
        long product = 1;
        int res = 0;

        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];

            while (product >= k) {
                product /= nums[left];
                left++;
            }

            res += right - left + 1;
        }

        return res;
    }
}

func numSubarrayProductLessThanK(nums []int, k int) int {
	if k <= 1 {
		return 0
	}

	left := 0
	product := 1
	res := 0

	for right, val := range nums {
		product *= val

		for product >= k {
			product /= nums[left]
			left++
		}

		res += right - left + 1
	}

	return res
}

相似题目

题目	难度	考察点
209. 长度最小的子数组	中等	滑动窗口
904. 水果成篮	中等	滑动窗口
992. K 个不同整数的子数组	困难	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
560. 和为 K 的子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/56411440