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%
版权声明:本文为Stack_Alan原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。