每日一题系列（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)的时间复杂度，理解滑动窗口的本质才有助于你解决类似问题不会毫无思路。
