【优选算法】9----长度最小的子数组

题目解析：

重点：在学习滑动窗口这一类算法题前，我们需要了解一个概念：“滑动窗口”是什么？

我们来用寻宝藏来设想一下：

滑动窗口就像是一个会自动调整大小的“魔法窗口”，在数组上滑动，寻找宝藏。它能大大减少不必要的计算，效率比暴力解法高多了。

讲解算法原理：

方法一：暴力解法：简单粗暴的大搜索

这题的解题思路就像是找宝藏，一开始咱两眼一抹黑，不知道宝藏在哪，那就得从最开始的地方一

点点摸索。

暴力解法很直接，就是把所有可能的子数组都找出来，计算它们的和，看看哪个子数组的和大于等

于 target ，然后找出其中长度最小的。这就好比把整个森林里的每一个角落都翻个遍，肯定能找

到宝藏，但就是有点费时间和精力。

方法二：聪明的寻宝法

这里的 left 和 right 就是滑动窗口的左右边界。一开始，窗口大小为 0 ，也就是 left 和 right 都在

数组的起始位置。然后，right 开始向右移动，就像把窗口一点点扩大，把新的数字装进窗口里，

同时累加窗口内数字的和。当窗口内数字的和大于等于 target 时，就说明找到了一个可能的“宝藏

序列”，这时候就尝试把窗口左边的边界 left 向右移动，看看能不能把窗口缩小，同时保持和大于

等于 target 。每缩小一次，就更新一下最小长度。这样不断地滑动窗口，就能找到满足条件的最

小子数组长度啦。

滑动窗口的时间复杂度是 O(n) ，因为每个元素最多进窗口和出窗口各一次，效率比暴力解法高了

不知道多少倍，就像开着跑车在森林里找宝藏，又快又准！

编写代码：

方法二如下所示：

​
​
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
       int n=nums.size(),sum=0,len=INT_MAX;
       for(int right =0,left=0;right<n;right++)
       {
        sum+=nums[right];
        while(sum>=target)
        {
            len=min(len,right-left+1);
            sum-=nums[left++];
        }
       }
       return len==INT_MAX?0:len;
    }
};

​

​

这道长度最小的子数组题目，通过暴力解法和滑动窗口两种思路的对比，让我们看到了算法优化的

魅力。暴力解法虽然简单易懂，但在效率上输给了滑动窗口。就像生活中，有时候简单直接的方法

虽然能解决问题，但多花点心思，找到更巧妙的方法，往往能事半功倍。

希望大家都能学会这个滑动窗口的技巧，以后再遇到类似的问题，就能轻松解决啦！