713. 乘积小于K的子数组

问题

给定一个正整数数组 \(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;
    }
}