本期知识点导图
1. 上期参考代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ret{};
for (int i = 0; i < n;) {
for (int j = i + 1; j < n;) {
int left = j + 1;
int right = n - 1;
long long aim = (long long)target - nums[i] - nums[j]; // 防止溢出
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < aim) left++;
else if (sum > aim) right--;
else {
ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
while (left < right && nums[left] == nums[left - 1]) left++; // 双指针去重
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
j++;
while (j < n && nums[j - 1] == nums[j]) j++; // 对 j 去重
}
i++;
while (i < n && nums[i - 1] == nums[i]) i++; // 对 i 去重
}
return ret;
}
};
注意： 计算 aim 时可能会发生数据溢出。
在主流编译器中：
| 类型 | 标准最小位数 | 取值范围 | 十进制 |
|---|---|---|---|
int | 16 位 | -2^31 ~ 2^31-1 | -2.1410^9 ~ 2.1410^9 |
long long | 64 位 | -2^63 ~ 2^63-1 | -9.2210^18 ~ 9.2210^18 |
取极端情况，显然会导致数据溢出。
此外，去重时防越界的判断条件要放到前边。当不满足条件时，直接短路，否则在执行第二个逻辑判断时会造成访问越界。
2. 题目解析
本期讲解的题目是 长度最小的子数组。
重点：
- 正整数数组
- 要找满足条件的（和 >= target）、最小的、连续的子数组
- 找到了返回子数组长度，找不到返回 0
3. 解题思路
3.1 暴力解法
整体思路是穷举所有子数组，找到最小符合条件的子数组，并返回最小长度。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int length = n + 1; // 设置一个不可能达到的长度
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = 0; // 每次进来先刷新 sum
int k = i;
while (k <= j) { // 累加 i 到 j 区间里面的值
sum += nums[k++];
}
if (sum >= target) { // 取最小值
int temp = j - i + 1;
length = min(temp, length);
}
}
}
return length == n + 1 ? 0 : length;
}
};
此算法的时间复杂度为 O(N^3)，必然超时。
3.2 优化算法
模拟暴力算法
我们先来模拟一下暴力解法，在此基础上探索更加优秀的算法。
暴力解法的整体框架是套三层循环：
- 第一层固定子数组的左区间
- 第二层枚举子数组的右区间
- 第三层对区间里的元素求和
我们用题给示例模拟一下： 定义一对双指针，模拟前两层的穷举工作，并尝试寻找优解：
left 固定左区间，right 向右遍历枚举右区间。遍历的过程中对区间里面的元素求和。
当 right 遍历到 2 时，得到符合要求的子数组：
两个优化点：
刷新 length 之后，right 继续向后遍历，我们将会发现，后边的子数组都必然满足条件。这是因为，数组里的元素全是正数，求和只会越来越大（单调性），但是区间长度会越来越长。我们要找的是最小子数组，所以当 right 遍历到符合要求的右区间之后，就不必要继续向后遍历了。此为优化点 1。（此时就可以用双指针算法来代替循环了）
这时我们让 left++，固定新的左区间，枚举右区间，重复前边的逻辑。这边要注意的是，求新的区间的元素和，不必让 right 返回到 left 处重新开始遍历区间内元素求和，我们只需要把退出区间的元素，也就是之前的 left 指向的元素减去即可。当然此次 left++ 之后，也要进行逻辑判断看此时的子数组是否依然满足条件，也就是说要进行循环，此为优化点 2。（规避了第三层的求和循环）
时间复杂度分析
经过此两次优化，我们发现，使用双指针似乎还是要嵌套两层循环（right 向右遍历 & 逻辑判断）才能解决问题，时间复杂度似乎是 O(N^2)。但是我们的暴力算法也可以通过优化点 2 来规避第三层循环，时间复杂度也是 O(N^2) 啊，使用双指针的优势在哪里？
我们判断时间复杂度不能只看嵌套的循环数，我们要看实际上执行了多少条代码。我们使用优化之后的暴力解法，前两个循环必然是实打实地执行了 0.5n(n-1) 次内循环的语句（信息维护和逻辑判断的语句），每次内循环都要重头开始遍历。但是我们使用双指针的话，我们遍历过程中，在每次进行完判断之后，一次只移动一个指针，right 指针至多移动 n 次（只往右走），left 指针至多移动 n 次（只往右走），也就是说，至多也就执行 n+n 次 信息维护和逻辑判断的语句。他们用大 O 渐进表示法分别就是，O(N^2) 和 O(N)。
4. 滑动窗口
4.1 是什么
说白了，就是**'同向双指针'**。
什么是双指针，应该不用我多说了，双指针一个指向窗口的左端点，一个指向窗口的右端点，两端点及其中间的内容所包含的元素就是我们要维护的窗口信息。
什么是同向，就是都只向同一个方向移动，在本题中的 left 和 right 的移动方式就是同向。
为什么叫滑动双指针呢？ 当同向双指针在数组中移动的时候，就像一个'移动'的窗口一样，窗口里面的内容不断地在改变（进出窗口），我们看到的（维护的）信息就不断在改变，就像我们坐高铁的时候，透过窗口向外看，看到的风景不断从窗口的一端进来，从另一端出去一样。
4.2 什么时候用
像本题，当窗口中的需维护的信息成单调性的时候（比如我们这里的求子数组的元素和，right 向右移动（元素进窗口），和成单调增的情形），我们可以考虑使用滑动窗口来解决问题。
本质上是造成双指针的同向移动
4.3 怎么用
- 初始化两个同向双指针充当窗口的左右端点。
- 元素进窗口（
right++），维护信息（sum） - 判断是否要出窗口（
left++）
在滑动窗口的时候（第二步和第三步）我们要更新结果（length）。当然更新结果是要就题论题的，可能是在进窗口之后出窗口之前，也可能是出窗口之后。本题是在信息维护的时候，也就是进窗口之后，出窗口之前更新结果。
5. 完整代码实现
基于上述思路，以下是完整的 C++ 滑动窗口解法：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int ans = INT_MAX;
int sum = 0;
int left = 0;
for (int right = 0; right < n; ++right) {
sum += nums[right]; // 元素进窗口
while (sum >= target) { // 判断是否需要出窗口
ans = min(ans, right - left + 1); // 更新结果
sum -= nums[left]; // 元素出窗口
left++;
}
}
return ans == INT_MAX ? 0 : ans;
}
};
6. 小结
本期在模拟穷举算法的过程中一步步推导，通过两个优化点，引出滑动窗口的概念（即同向双指针）。并介绍了滑动窗口的用法。这是滑动窗口专题的第一个算法，大家要重点掌握'窗口'思维，最好自己画画图，模拟一下滑动窗口的过程，并尝试代码的实现。
