Leetcode--Java--713. 乘积小于 K 的子数组

题目描述

给你一个整数数组 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. 基本思想：考虑对于每个位置的元素，如果作为一段子数组的结尾，可以形成多少个满足要求的子数组。
2. 用滑动窗口寻找最大的满足要求的，然后求以最后位置结尾的所有子数组（其实就是长度），如果超出，则移动左端端点（并删除累成到临时积中的数）
3. 维护一个临时积，表示当前滑动窗口的乘积

代码

class Solution {
          
   
    public int numSubarrayProductLessThanK(int[] nums, int k) {
          
   
        int n = nums.length, res = 0;
        if (k <= 1) {
          
   
            return 0;
        }
        for (int i = 0, j = 0, curSum = 1; i < n; i ++ ) {
          
   
            curSum *= nums[i];
            //若窗口内大于等于规定数，则移动左边窗口
            while (curSum >= k) {
          
   
                curSum /= nums[j ++ ];
            }
            //统计当前窗口内以nums[i]，结尾的[j, i]内的子数组，其实就是这段长度
            res += i - j + 1;
        }
        return res;
    }
}