首页 > 科技 > 「leetcode系列」第二十九期 乘积小于K的子数组

「leetcode系列」第二十九期 乘积小于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

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

setTimeout(function () { fetch('http://www.sosokankan.com/stat/article.html?articleId=' + MIP.getData('articleId')) .then(function () { }) }, 3 * 1000)