[数据结构与算法]713. 乘积小于 K 的子数组（ 经典滑动窗口 ）

Question

713. 乘积小于 K 的子数组

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-product-less-than-k/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Ideas

1、Answer( Java )

解法思路：滑动窗口

👍当前元素合法的子数组数目 = 滑动窗口中元素的个数

Code

/**
 * @author Listen 1024
 * @description 713. 乘积小于 K 的子数组 (典型滑动窗口)( subarray子数组必须是连续的 ) ( subsequence子序列可以不是连续的 )
 * 题目条件 1 <= nums[i] <= 1000
 * 时间复杂度O(n)
 * 空间复杂度O(1)
 * @date 2022-05-05 8:42
 */
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0;
        int curValue = 1;
        int start = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= k) {
                start = i + 1;//将移动滑动窗口的左端移动到当前元素的右边
                curValue = 1;
            } else {
                curValue *= nums[i];
                while (curValue >= k) {
                    curValue /= nums[start];//缩短窗口的左端
                    start++;
                }
            }
            if (curValue < k) {
                res += i - start + 1;//更新结果(当前元素的符合条件的子数组数目 = 滑动窗口中元素的个数)
            }
        }
        return res;
    }
}

/**
 * @author Listen 1024
 * @description 713. 乘积小于 K 的子数组 (典型滑动窗口)( subarray子数组必须是连续的 ) ( subsequence子序列可以不是连续的 )
 * 题目条件 1 <= nums[i] <= 1000
 * 时间复杂度O(n)
 * 空间复杂度O(1)
 * @date 2022-05-05 8:42
 */
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int res = 0, curValue = 1;
        if (k <= 1) {
            return 0;
        }
        for (int i = 0, j = 0; i < nums.length; i++) {
            curValue *= nums[i];
            while (curValue >= k) {
                curValue /= nums[j++];
            }
            res += i - j + 1;
        }
        return res;
    }
}

//部分题解参考链接(如侵删)
https://leetcode-cn.com/problems/subarray-product-less-than-k/solution/by-ac_oier-3w08/

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖