作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
上一篇文章当中我们接触了两指针算法，在上一篇文章当中，我们使用了一快一慢两个指针来访问数组，从而避免了删除元素时需要移动数组的巨大开销。
除了可以理解成快慢指针之外，我们还可以换个角度，从区间的层面入手。慢的指针维护了一个全部不等于val的区间，它会在遇到val时停下，而快的指针维护的就是能够覆盖慢指针遇到的val的位置。本质上还是利用两个指针来维护区间，两指针算法的例题已经应用方法千变万化，但不论怎么变化，底层的核心是恒定的，就是用两个指针维护一个潜在的区间。
同样，我们来看一道例题——LeetCode209。
209 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl 1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
分析
首先我们还是先来暴力，我们使用l和r表示区间的左右两个端点，接着我们遍历左右两个端点内的所有元素进行求和。写出来代码如下：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = n 1;
for (int l = 0; l < n; l ) {
for (int r = l; r < n; r ) {
int tmp = 0;
for (int i = l; i <= r; i ) {
tmp = nums[i];
}
if (tmp >= target) ret = min(ret, r - l 1);
}
}
return ret > n ? 0 : ret;
}
};
在这个算法当中我们用到了三重循环，复杂度是
，在本题的数据范围当中一定会超时。
优化
有些同学可能会很容易想到优化：我们这里使用了一重循环去单独计算下标区间[l, r]对应的元素和，我们完全可以引入前缀和数组，这样就可以在
的复杂度内计算出区间和。于是算法的复杂度可以蜕化成
。
前缀和固然好用，但消耗了额外的存储空间。其实我们完全可以做到在不引入额外空间的基础上将复杂度优化到
。因为本题当中明确说了希望我们寻找最小的连续子数组，我们可以固定左侧端点，移动右侧端点来计算区间和。当满足总和大于等于target时，就可以提前break了，因为已经达到要求了，再往后遍历得到的区间一定不是最小的。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = n 1;
for (int l = 0; l < n; l ) {
int tot = 0, r = l;
// 当不满足要求时，移动右侧端点，更新区间和
while (r < n && tot < target) {
tot = nums[r ];
}
if (tot >= target) ret = min(ret, r - l);
}
return ret > n ? 0 : ret;
}
};
到这里可能会有同学会说，说了这么一大通有什么用，算法的复杂度还是
，在本题当中一样会超时。
思考
别着急，我们在解题的过程当中最忌讳的不是一种方法不奏效，而是觉得好像不奏效就不继续深入思考了。很多时候正解正是从这些看起来可能不太奏效的方法当中推导得到的。
所以让我们冷静下来，继续思考，现在还有哪里可以优化呢？
答案是我们的求和过程时可以优化的，在第一轮循环当中，l=0，我们计算的是区间[0, r]的区间和。第二轮循环时，l移动到了1，我们计算的是[1, r']的区间和，其中r' >= r。很明显，这两个区间当中[1, r]的部分我们是重复计算的。随着l继续循环，一直会有这样重复计算的区间存在。
那么，既然如此，我们有没有办法可以跳过这些冗余的部分呢？
当然有！
从单点到区间
在学习这个算法之前，我们每次使用循环，无非是遍历或累加。这两种方式本质上都是围绕单点展开的，这里我们要跳出思维的桎梏，同样是使用循环，我们不再关注一个具体的点，而关注一个区间。
一旦我们拥有了关注区间的思维，就会发现我们其实已经离正解很接近了。
在上面的暴力算法当中，我们先遍历了左侧端点l，接着又遍历了右侧端点r以此来获得它们之间的区间和。我们假设以l为左侧端点的区间和满足大于等于target时，对应的最小的右端点是r。从全局来看，这个[l, r]的区间不一定是最优的，所以我们还要遍历其他的区间。
我们先不去想具体要怎样寻找，我们先来思考一个问题，我们知道了l对应的右端点是r。那么l 1的左端点对应的最佳右端点r'是什么？在本题当中，我们可能不能直接知道r'的取值，但我们可以给出判断r' >= r。因为本题中nums数组中的值都是正数，左侧端点从l移动到l 1的过程当中，少加了nums[l]。所以要使得总和能够大于等于target的话，一定能得出r' >= r。
以此类推，当我们l从左往右移动的过程当中，对应的r也是递增的。既然如此，我们完全没必要每次都将r移动到l。
想通了这一层之后，你会发现我们只需要在之前的代码上做非常小的修改，就可以将复杂度降低到
。因为r不再移动到l，所以l和r都是递增的，一共最多只能执行
次，所以算法的复杂度是
。
代码语言：javascript复制class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = n 1;
int tot = 0, r = 0;
for (int l = 0; l < n; l ) {
while (r < n && tot < target) {
tot = nums[r ];
}
if (tot >= target) ret = min(ret, r - l);
// l移动之后要从总和当中去除
tot -= nums[l];
}
return ret > n ? 0 : ret;
}
};
当然，我们也可以换一种写法，每次移动区间的右侧端点。这样每次移动了r之后都会引入新的元素，当达成条件之后，我们需要移动左侧端点，查看是否存在更优的情况。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int tot = 0, l = 0;
int ret = n 1;
// 移动右侧端点
for (int r = 0; r < n; r ) {
tot = nums[r];
// 当满足>=target时，移动左侧，查看是否有更优的区间
while (l <= r && tot >= target) {
ret = min(ret, r - l 1);
tot -= nums[l ];
}
}
return ret > n ? 0 : ret;
}
};
这两段代码虽然写法不同，但是内核原理是一样的。这个时候我们可以总结一下算法的套路，首先，我们确定一个初始的区间。接着我们每次移动其中一边，在保证区间符合题目要求的同时移动另一侧指针。
注意，我们要保证区间的两个指针移动是同方向的，右指针往右移动，在维护区间时需要左指针也往右。同理，如果是左指针往右，需要右指针也往右。
在一些算法书中这样的算法被叫做滑动窗口，也有的叫做two pointers或者尺取法。不管叫什么名字，核心原理是一样的。以后遇上寻找最优区间的问题时，可以往这上面思考，也许一下子就能解出来了。
最后，感谢大家的阅读，如果喜欢的话，恳请帮忙转发扩散。算法学习之旅，与你同行。
