【LeetCode】乘积小于 K 的子数组 Java 题解

2022 年 5 月 11 日
本文字数：1005 字
阅读完需：约 3 分钟

题目描述

给你一个整数数组 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
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/subarray-product-less-than-k著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组处理题目，题目要求返回子数组内所有元素的 乘积严格小于 k 的 连续子数组 的数目。
根据这两个重要的条件，我们首先可以采用普通解法，依次遍历每一个数组元素，求乘积小于 k 的连续子数组个数，实现代码如下。
分析普通解法，发现计算乘积的过程中有重复计算，我们可以优化这部分，由于是求连续子数组，我们可以转换成为滑动窗口的问题，采用双指针思想，动态变化范围求解，实现代码如下，供参考。

通过代码

普通解法

class Solution {    public int numSubarrayProductLessThanK(int[] nums, int k) {        int ans = 0;        int n = nums.length;
        for (int i = 0; i < n; i++) {            if (nums[i] < k) {                ans++;            }            int temp = nums[i];            for (int j = i + 1; j < n; j++) {                temp *= nums[j];                if (temp < k) {                    ans++;                } else {                    break;                }            }        }
        return ans;    }}

复制代码

滑动窗口

class Solution {    public int numSubarrayProductLessThanK(int[] nums, int k) {        int ans = 0;        int n = nums.length;        int left = 0;        int current = 1;        for (int right = 0; right < n; right++) {            current *= nums[right];            while (left <= right && current >= k) {                current /= nums[left];                left++;            }            ans += (right - left + 1);        }
        return ans;    }}