滑动窗口相关题解
1. 长度最小的子数组
算法思路一（暴力）（超时）：
【从前往后】枚举数组中的任意一个元素，把它当成起始位置。然后从这个【起始位置】开始，寻找一段最短的区间，使得这段区间的和【大于等于】目标值。
将所有元素作为起始位置所得的结果中，找到【最小值】即可。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ret = INT_MAX;
int n = nums.size();
for (int start = 0; start < n; start++) {
int sum = 0;
for (int end = start; end < n; end++) {
sum += nums[end];
if (sum >= target) {
ret = min(ret, end - start + 1);
break;
}
}
}
return ret == INT_MAX ? 0 : ret;
}
};
算法思路二（滑动窗口）：
由于此问题分析的对象是【一段连续的区间】，因此可以考虑【滑动窗口】的思想来解决这道题。让滑动窗口满足：从 i 位置开始，窗口内所有元素的和小于 target（那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度）。
做法：将右端元素滑入窗口中，统计出当前窗口内的元素的和：
- 若窗口内元素之和大于等于 target：更新结果，并将左端元素滑出的同时继续判断是否满足条件并更新结果（因为左端元素可能很小，滑出去之后依旧满足条件）
- 若窗口内元素和不满足条件：right++，下一个元素进入窗口
为什么滑动窗口可以解决问题，并且时间复杂度低？
- 这个窗口寻找的是：以当前窗口最左侧元素（记为 left1）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满足区间 sum>= target 时的最右侧（记为 right1）能到哪里。
- 我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 left1。但是若继续像方法一一样，重新开始统计 left1 的下一元素（left2）往后的和，一定会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和，这些和是可以在计算下次区间和的时候用上的）。
- 此时，right1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从 right1 这个元素开始，往后找满足 left2 元素的区间（此时 right1 也有可能是满足的，因为 left1 可能很小。sum 剔除掉 left1 之后，依旧满足大于等于 target）。这样我们就能省掉大量重复的计算。
