跳至主要內容

最小长度子数组和

linwu大约 2 分钟

最小长度子数组和

给定一个正整数数组nums和一个正整数target,找出数组中满足其和≥target的最短子数组的长度,如果不存在满足条件的子数组,返回0。

示例:

输入:nums = [2,3,1,2,4,3],target = 7 输出:2 解释:子数组 [4,3] 的和为 7,且长度最小。

输入:nums = [1,4,4],target = 4 输出:1 解释:子数组 [4] 的和为 4,且长度最小。

题目分析与解题步骤:

这个问题可以使用滑动窗口算法来解决。我们可以维护一个窗口,不断地向右扩展窗口,直到窗口内的元素和≥target。然后,我们尝试将窗口的左边界向右收缩,以寻找更短的满足条件的子数组。

解题步骤如下:

  1. 初始化两个指针leftright,都指向数组的开始位置。初始化窗口的和windowSum为0,最小子数组的长度minLength为无穷大。

  2. 不断向右移动right指针,扩大窗口。在每次移动时,将当前元素添加到窗口的和windowSum中。

  3. 当窗口的和≥target时,更新最小子数组的长度minLength为当前窗口的大小,并尝试将窗口的左边界向右收缩。

  4. 在收缩窗口时,从窗口的左边界开始,将左边界的元素从窗口的和windowSum中减去,并将左边界向右移动。

  5. 重复步骤2-4,直到right指针到达数组的末尾。

  6. 返回最小子数组的长度minLength。如果不存在满足条件的子数组,返回0。

JavaScript解题框架:

function minSubArrayLen(nums, target) {
    let left = 0;
    let minLength = Infinity;
    let windowSum = 0;

    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];

        while (windowSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

在这个框架中,我们使用leftright两个指针来构建窗口,windowSum用于记录窗口内元素的和,minLength记录最小子数组的长度。

我们不断向右移动right指针,将当前元素添加到窗口的和windowSum中。当windowSumtarget时,我们尝试收缩窗口,从窗口的左边界开始,将左边界的元素从windowSum中减去,并将左边界向右移动。在每次收缩窗口时,我们更新最小子数组的长度minLength为当前窗口的大小。

最后,返回minLength作为结果。如果不存在满足条件的子数组,返回0。

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群