算法 职场和发展 LeetCode刷题笔记 - JavaScript（七）

文章目录

1.剑指 Offer II 008. 和大于等于 target 的最短子数组2.剑指 Offer II 009. 乘积小于 K 的子数组3.剑指 Offer II 010. 和为 k 的子数组

剑指 Offer II 008. 和大于等于 target 的最短子数组 剑指 Offer II 009. 乘积小于 K 的子数组 剑指 Offer II 010. 和为 k 的子数组

1.剑指 Offer II 008. 和大于等于 target 的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

题目大意：求和>=target的最短子数组的长度。

解题思路：滑动窗口。维护一个小于target的值，当值>=target时，更新res。

代码：

var minSubArrayLen = function(target, nums) {

const INT_MAX = Math.floor(Math.pow(2,31))-1;

let res = INT_MAX;

let l = 0, r = 0;

let temp = 0;

while(r < nums.length) {

temp += nums[r];

while(temp >= target) {

res = Math.min(res, r - l + 1);

temp -= nums[l];

l++;

}

r++;

}

return res === INT_MAX ? 0 : res;

};

2.剑指 Offer II 009. 乘积小于 K 的子数组

给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。

题目大意：求乘积小于k的所有连续子数组。

解题思路：滑动窗口，维护一个

代码：

var numSubarrayProductLessThanK = function(nums, k) {

let res = 0;

let l = 0, r = 0;

let temp = 1;

while(r < nums.length) {

temp *= nums[r];

while(temp >= k) {

temp /= nums[l];

l++;

}

if(temp < k)res += r-l+1;

r++;

}

return res;

};

3.剑指 Offer II 010. 和为 k 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

题目大意：求和为k的所有子数组。

解题思路：Map优化前缀和。

代码：

var subarraySum = function(nums, k) {

let res = 0;

let pre = 0;

const mp = new Map();

mp.set(0,1);

for(const num of nums) {

pre += num;

if(mp.has(pre - k)) {

res += mp.get(pre-k);

}

mp.has(pre) ? mp.set(pre, mp.get(pre) + 1) : mp.set(pre,1);

}

return res;

};

相关文章

 您阅读本篇文章共花了：