算法(5)-长度最小的子数组和滑动窗口

数组

 2024/03/06 

题目(medium)：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路

暴力求解是两层 for 循环遍历，时间复杂度是 O(n^2)，空间复杂度是 O(1)。

滑动窗口

就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

const minSubArrayLen = (target, nums) => {
    let start = 0;
    let end = 0;
    let sum = 0;
    let len = nums.length;
    let ans = Infinity;
    while(end < len) {
        sum += nums[end];
        while(sum >= target) {
            ans = Math.min(ans, end - start + 1);
            sum -= nums[start];
            start++;
        }
        end++;
    }
    return ans === Infinity ? 0 : ans;
}

时间复杂度：O(n)。
空间复杂度：O(1)。

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/06/2024-03-06-%E7%AE%97%E6%B3%95(5)-%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84%E5%92%8C%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3/

发表日期：March 6th 2024, 10:51:34 pm

更新日期：March 11th 2024, 12:07:37 pm

Next Post

算法(6)-螺旋矩阵 II
Previous Post

算法(4)-有序数组的平方与左右指针

CATALOG

1. 题目(medium)：
2. 思路
1. 2.1. 滑动窗口