博客

leetcode刷题

713. 乘积小于 K 的子数组

题目

给你一个整数数组

nums

和一个整数

k

，请你返回子数组内所有元素的乘积严格小于

k

的连续子数组的数目。

分析

使用双指针，遍历right，当[left:right]的乘积大于等于k时，[left:right]的所有子连续数据皆满足题意

(1+right-left) * (right-left) / 2

个，但是有一部分[left:last_right]（当前left到上一次的right）的子数组被重复算了一次，需要去掉

1+point-left) * (point-left) / 2

。此时，需要依次挪到left，直至乘积小于k。

重复上述运算直至right到头，最后判断[left:right]是否<k，满足则加入。因为没有触发内部num>k的条件。

代码

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if(k==0) return 0;
    int left=0;
    int right=0;
    int point = 0;
    int count = 0;
    int num = 1;
    while (right<nums.length){
        num *= nums[right];
        if (num>=k){
            count += (1+right-left) * (right-left) / 2 - (1+point-left) * (point-left) / 2;
            point = right;
            while(left<nums.length && num>=k && left<=right){
                num /= nums[left];
                left++;
            }
        }
        right++;
    }
    if (num<k)
        count += (1+right-left) * (right-left) / 2 - (1+point-left) * (point-left) / 2;
    return count;
}

结果

时间超过39%

内存超过80%