每日一题：LeetCode-209. 长度最小的子数组（滑动窗口）

每日一题系列（day 11）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

   🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

题目：

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

示例：

  提示：

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

解法一：

  思路：

  根据示例我们可以了解到，这题是让我们求一个最短的子数组，并且保证这个子数组元素的和要>= target值的。

  我们可以使用两个指针当做数组的左右区间，用left，right指针指向数组的下标，left表示左区间，right表示右区间，用sum值计算每次移动区间之后区间元素值的和，最后遍历完返回最小区间数组。

  O(n^3)的时间复杂度还是太大了，我们还能不能再暴力的基础上再优化呢？，其实我们仔细观察，那个求和的O(n)似乎还有优化的空间。
  在right移动的时候我们可以记录下来每一次计算的sum值，right向后移动一位我们只需要在前面sum的基础上加上right下一位的值即可，同理，当left向后移动一位的时候，我们只需要在sum的基础上减去left移动之前的值。
  除此之外，我们其实当sum的值大于等于target值的时候right就可以不用再向后移动了，因为这个时候你的区间值的和已经大于了target值，right往后遍历只会让区间增大，所以没有遍历的必要了，直接开启下一轮的循环。left++

  当区间的sum值要大于等于target的值的时候，我们就需要更新区间ans的值了，如果本次区间的ans要小于之前记录的最小区间，则将区间更新为本次区间大小，表示到目前为止，最小符合条件的区间为当前区间。这样遍历到最后，我们就能得到符合条件的最小区间了。

  这样我们暴力枚举的时间复杂度就降为O(n^2)了。

  代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();//nums数组长度
        if(n == 0) return 0;
        int ans = INT_MAX;//长度设置为整形的最大值，防止误判
        for(int i = 0 ; i < n ; i++)
        {
            int sum = 0;
            for(int j = i ; j < n ; j++)//i,j就是左右指针
            {
                sum += nums[j];//sum进行累加
                if(sum >= target)
                {
                    ans = min(ans, j - i + 1);//保留较小的区间
                    break;//终结本次循环
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;//防止误判
    }
};

  可以看到我们的测试用例过了，但是我们的执行结果却超时了，这说明我们的时间复杂度就太高了，我们应该想一想其他的方法来降低时间复杂度，这就是我接下来要说的————滑动窗口

解法二：

  思路：

  其实整体思路和上面差不多，不过滑动窗口的left和right都是在向右移动，right指针没有回退的操作，这种“同向双指针” ，也被称为滑动窗口，其实很形象，左右指针一直同向移动，看起来就像是在滑动的窗口，故此得名。

  我们可以看到，如果是最坏的情况，也就是左右指针把数组都遍历一遍，也就是O(2n)时间复杂度，也就是 O(N) 级别的时间复杂度，空间上只用了几个变量，所以 空间复杂度为O(1)，相比较之下，我们的滑动窗口确实非常好用。

  代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int n = nums.size();
        int len = INT_MAX, sum = 0;
        while(right < n)
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right - left + 1);//比较找出最小区间
                sum -= nums[left++];
            }
            right++;
        }
        return len == INT_MAX ? 0 : len;
    }
};

  今天是第一次写滑动窗口的题，果然非常奇妙，居然只有O(N)的时间复杂度，理解滑动窗口的本质才有助于你解决类似问题不会毫无思路。