LeetCode 209. 长度最小的子数组(两种解法)(贪心 + 双指针)—— JavaScript
程序员文章站
2022-06-19 15:48:51
题链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum/题描述:解题思路(贪心):遍历数组,每次从当前元素开始,往后累加元素值,如果累加值大于等于 s,这一段就是符合条件的子数组,最后返回最短的长度即可。代码实现(贪心):/** * @param {number} s * @param {number[]} nums * @return {number} */var minSubArrayLen = f...
题链接:https://leetcode-cn.com/problems/minimum-size-subarray-sum/
题描述:
解题思路(贪心):
遍历数组,每次从当前元素开始,往后累加元素值,如果累加值大于等于 s,这一段就是符合条件的子数组,最后返回最短的长度即可。
代码实现(贪心):
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
let res = nums.length + 1;
for (let i = 0; i < nums.length; i++) {
let t = 0;
for (let j = i; j < nums.length; j++) {
t += nums[j];
if (t >= s) {
res = j - i + 1 < res ? j - i + 1 : res;
}
}
}
return res == nums.length + 1 ? 0 : res;
};
时间复杂度:O(n^2)
空间复杂度:O(1)
解题思路(双指针):
定义 left 和 right 指针表示子数组的左右边界位置,sum 变量存储 nums[left] — nums[right] 的和。
left、right 和 sum 初始化为 0。
每次将 right 向右移一位,当 left 到 right 的子数组的和大于等于 s 时,就开始移动 left 指针,因为每次是从 left 位置上的元素开始子数组的值的累加,所以子数组和大于等于 s 时,就将下一位元素作为子数组的起始元素,在这个迭代的过程中,会实时维护更新最短的子数组的长度。
代码实现(双指针):
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function(s, nums) {
let res = nums.length + 1;
let left = 0;
let right = 0;
let sum = 0;
while (right < nums.length) {
sum += nums[right];
while (sum >= s) {
res = Math.min(res, right - left + 1);
sum -= nums[left];
left++;
}
right ++;
}
return res == nums.length + 1 ? 0 : res;
};
时间复杂度:O(n)
空间复杂度:O(1)
本文地址:https://blog.csdn.net/ySFRaabbcc/article/details/110949476