欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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/


题描述:

LeetCode 209. 长度最小的子数组(两种解法)(贪心 + 双指针)—— JavaScript


解题思路(贪心):

遍历数组,每次从当前元素开始,往后累加元素值,如果累加值大于等于 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;
};

LeetCode 209. 长度最小的子数组(两种解法)(贪心 + 双指针)—— JavaScript

时间复杂度: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;
};

LeetCode 209. 长度最小的子数组(两种解法)(贪心 + 双指针)—— JavaScript

时间复杂度:O(n)

空间复杂度:O(1)

本文地址:https://blog.csdn.net/ySFRaabbcc/article/details/110949476