LeetCode - 209 长度最小的子数组

灰太狼 2023-09-26 11:47 122阅读 0赞

**目录**

题目来源

题目描述

用例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[209. 长度最小的子数组 - 力扣（LeetCode）][209. _ - _LeetCode]

### 题目描述 ###

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

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

### 用例 ###

> 输入：target = 7, nums = \[2,3,1,2,4,3\]  
> 输出：2  
> 解释：子数组 \[4,3\] 是该条件下的长度最小的子数组。

> 输入：target = 4, nums = \[1,4,4\]  
> 输出：1

> 输入：target = 11, nums = \[1,1,1,1,1,1,1,1\]  
> 输出：0

### 提示 ###

*  `1 <= target <= 109`
 *  `1 <= nums.length <= 105`
 *  `1 <= nums[i] <= 105`

### 题目解析 ###

这题也很明显是可以利用滑动窗口解决的。

最简单的滑动窗口定义就是双重for，外层左指针，内层右指针，实现如下

> 需要注意题意，找的是 ≥ target的连续子数组，而不仅仅是＞target的连续子数组

/**
     * @param {number} target
     * @param {number[]} nums
     * @return {number}
     */
    var minSubArrayLen = function (target, nums) {
      let sum = 0;
      let minLen = 0;
    
      for (let left = 0; left < nums.length; left++) {
        sum = 0;
        for (let right = left; right < nums.length; right++) {
          sum += nums[right];
    
          if (sum >= target) {
            minLen =
              minLen === 0 ? right - left + 1 : Math.min(minLen, right - left + 1);
              break;
          }
        }
      }
    
      return minLen;
    };

![170e97722d1f4e31b3fa0f39e794ef9c.png][]

虽然算法最终符合题意，但是时间复杂度和空间复杂度都不理想。

上述算法性能不高的原因在于进行了大量重复的计算：

![3809ca514dbe41659b98de7a8c524170.png][]

比如left=1时，遍历的\[3\]、\[3,1\]子序列明显是包含在 left=0的\[2,3\]和\[2,3,1\]中，在left=0时已经验证了\[2,3\]、\[2,3,1\]不符合要求了，因此\[3\]、\[3,1\]可以直接判断出来不符合题意，而不需要再次判断。同理如上图中画圈的都是冗余判断。去除上面冗余判断，可得

![70716ef6f4d247d49aa6cfc7c10c9efe.png][]

因此我们可以得出结论，当滑动窗口符合要求后，则右指针位置不动，左指针向右移动一位，如果此时滑动窗口内容不符合要求了，右指针再移动，否则左指针继续向右移动。直到左指针到达尾部终止。

算法实现如下源码所示

### 算法源码 ###

/**
     * @param {number} target
     * @param {number[]} nums
     * @return {number}
     */
    var minSubArrayLen = function (target, nums) {
      let sum = 0;
      let minLen = 0;
    
      let left = 0;
      let right = 0;
    
      while (right < nums.length) {
        sum += nums[right];
        while (sum >= target) {
          minLen =
            minLen === 0 ? right - left + 1 : Math.min(minLen, right - left + 1);
    
          sum -= nums[left];
          left++;
        }
        right++;
      }
    
      return minLen;
    };

![182da844467a43b89843846c2eb8d638.png][]

此时算法时间复杂度有了大幅提升。

[209. _ - _LeetCode]: https://leetcode.cn/problems/minimum-size-subarray-sum/
[170e97722d1f4e31b3fa0f39e794ef9c.png]: https://img-blog.csdnimg.cn/170e97722d1f4e31b3fa0f39e794ef9c.png
[3809ca514dbe41659b98de7a8c524170.png]: https://img-blog.csdnimg.cn/3809ca514dbe41659b98de7a8c524170.png
[70716ef6f4d247d49aa6cfc7c10c9efe.png]: https://img-blog.csdnimg.cn/70716ef6f4d247d49aa6cfc7c10c9efe.png
[182da844467a43b89843846c2eb8d638.png]: https://img-blog.csdnimg.cn/182da844467a43b89843846c2eb8d638.png