问题

给定一个正整数数组 \(nums\)。
找出该数组内乘积小于 \(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的子数组。

说明:

• \(0 < nums.length <= 50000\)
• \(0 < nums[i] < 1000\)
• \(0 <= k < 10^6\)

解法

第一想法是使用双指针一直乘，当结果小于\(k\)时，将\(fast\)指针与\(slow\)指针之间的子数组数量加到结果\(result\)中。但是难点在于如何排重。
我们会注意到这样一种规律：

• 当\(fast\)等于\(slow\)时，其实只有一种子数组就是\([nums[fast]]\)
• \(fast\)与\(slow\)之间的全部子数组，必然包含所有的\(fast-1\)与\(slow\)之间的子数组

此时会发现，\(fast\)与\(fast-1\)子数组的区别仅在于是否包含\(nums[fast]\)元素，而包含全部\(nums[fast]\)元素的子数组数量为\(fast-slow+1\)，这个值，就排除了重复的子数组，\(result\)对这个数字进行暂存就可以在循环结束后直接得到数组数量。

可能说的有些乱，下面给出一个例子，\([1,2,3]\)数组，当\(slow=0,fast=2\)时，此时,全部的子数组为\([1],[2],[1,2]\)，当\(slow=0,fast=3\)时，此时的子数组为\([1],[2],[1,2],[1,2,3],[2,3],[3]\)，对比两个子数组可以发现，两者的区别就在于多了包含\(fast\)的元素的数组。

当乘积不满足条件时，乘积除以\(slow\)指针元素，\(slow\)指针前进，

代码

java代码

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // slow为慢指针，mul为slow与fast之间的乘积，result为满足条件的数组个数.
        int slow = 0, mul = 1, result = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            // fast指针前移，mul计算新的乘积。
            mul *= nums[fast];
            //此时判断mul是否已经大于k了，当大于时，需要除slow元素直到满足条件为止
            while (mul >= k && slow <= fast) {
                mul /= nums[slow++];
            }
            //这里可能会有疑问需不需要判断slow与fast的大小，其实这里不需要判断，前一步如果slow超过fast了，下一轮时，fast会赶上来。而且slow最多比fast多1，两者相减再加一等于0，符合数组数量为0，不用担心减成负数
            result += fast - slow + 1;
        }
        return result;
    }
}