713. 乘积小于K的子数组

问题

给定一个正整数数组 。
找出该数组内乘积小于 的连续的子数组的个数。

示例 1:

输入:
输出:
解释: 个乘积小于的子数组分别为: 。

需要注意的是 并不是乘积小于100的子数组。

说明:

解法

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

• 当等于时，其实只有一种子数组就是
• 与之间的全部子数组，必然包含所有的与之间的子数组

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

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

代码

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;
    }
}