题目正文
给定一个正整数数组 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
0
0
链接:https://leetcode-cn.com/problems/subarray-product-less-than-k
这道题目理解完之后并不难,使用2个指针,当乘积小于k时,右指针+1,大于或等于k时,左指针+1.这样可以在O(n)的时间复杂度内完成计算。
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numSubarrayProductLessThanK = function(nums, k) {
var l = 0;
var r = 0;
var p = 1; // 乘积
var c = 0; // 结果
for(var l = 0; l
p = p * nums[r];
while(p
c += r - l + 1;
r++;
if(r == nums.length){
break;
}
p = p * nums[r];
}
p = p / nums[l] / nums[r];
}
return c;
};
为2层循环,但是整体时间复杂度为O(n). 主要还是要看代码部分进行理解,中等难度,基本做过一遍就会记得。
算法题锻炼的是思维,以及积累相关经验,以对类似题目进行求解,和高中数学差不多,基本就是题海战术。
本文来自投稿,不代表本人立场,如若转载,请注明出处:http://www.sosokankan.com/article/1515088.html