209. 长度最小的子数组

209. 长度最小的子数组

先看屎山：

class Solution {
  public:
	int minSubArrayLen(int target, vector<int> &nums)
	{
		bool ever_succeeded = false;
		int n = static_cast<int>(nums.size()), min_len = n;
		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= min(min_len, n - i); j++) {
				int sum = 0;
				for (int k = i; k < i + j; k++) {
					sum += nums[k];
				}
				if (sum >= target) {
					ever_succeeded = true;
					min_len = j;
					break;
				}
			}
		}
		if (!ever_succeeded) {
			min_len = 0;
		}
		return min_len;
	}
};

是的，什么都不看的情况下，我造了坨$O(n^3)$的屎，也是必然的超时了。接下来我要学习了。

原来人家暴力枚举的时候不会重新求和？至少也是个$O(n^2)$？

真正的思想叫作滑动窗口？！没听说过！

---

从这道题开始了解滑动窗口。

上面的解法有2个n的因子可以优化：

1. 每一次框定数据范围以后，都从头到尾求了一次和：

for (int k = i; k < i + j; k++) {
	sum += nums[k];
}

完全可以在框定数据的过程中前前后后加加减减，不过在我的这种框定方式下，几乎不可能想到这样，能想到这样也就能想到滑动窗口。

2. 框定数据的方式，采用了两重循环暴力枚举。接下来看这个更优的框定数据方法。

实际上滑动窗口和双指针也有点像。但是在这里两个指针的作用是框定了一个数据的范围，因此使用“滑动窗口”来称呼，使用范围和双指针是不一样的。

好，接下来正式讲解这个算法的核心思想：

固定左端点i，然后不断右移右端点j，直到窗口内数据满足条件（和大于等于target）。此时，对于这个特定的i，最优解已经找到，这个j就是满足条件的最小。 所以接下来，可以右移i了。但是不像暴力枚举那样，没有把j拉回来重新右移，而是保持j在刚才的位置不动。为什么不需要回来？因为回来一定刚才要小啊。无论i右移几格，都不应该把j拉回来，因为一定不可能满足。应该趁现在，把i这一边的边界压到足够小，i一直走，一直走到不满足为止。那么最后一次满足就是最小的区间。然后继续这个循环，固定i，然后右移j，找到能够满足的。从数学上，这就一定可以找到最小区间，而不会有所遗漏。

下面用一个具体的例子来解释整个过程： target是13,一开始i和j都在0。然后j一顿移，移到5终于和大于等于了13.现在的区间是0~5. 接下来，i就要开始收缩了。i也一顿移，一直移到了4,此时不满足了，i在3的时候是最后一次满足的情况，是历史最短，3.

为什么在i移动的过程中，j不可以往左来获得可能更短的结果？因为在一开始i在0,j从0到5的这个过程中，已经试过了比它长的区间，那些区间都不能达到target，它又怎么可能达到target呢？所以说这是不用试的。 接下来，j继续右移，右移了一格到6就发现又满足了。 i开始收缩，i也移到了6,此时和是3,不满足了。i最后一次满足的地方是在5,此时长度为2,又是历史最短。

接下来要j继续右移了，但是j已经到达了边界。而刚才i已经收缩过了。所以全部找完了。最短的就是这个5~6,长度为2的子串。

完整代码

class Solution {
  public:
	int minSubArrayLen(int target, vector<int> &nums)
	{
		int i = 0, j = 0, sum = 0, n = nums.size(), res = n + 1;
		for (j = 0; j < n; j++) {
			sum += nums[j];
			while (sum >= target) {
				res = min(res, j - i + 1);
				sum -= nums[i++];
			}
		}
		if (res == n + 1) {
			res = 0;
		}
		return res;
	}
};

res = n + 1是什么？

这是一种方法，叫作“哨兵值”。给了一个不可能取到的值，在正常的滑动中，绝对不可能有比n+1还要大的值出现，所有的值都应该比他还要小。所以，如果这个值被修改了，说明我们找到了一种和的取法；如果他还保持着n+1原样，那说明他没有被动过，整个过程中也没有人去改过，即找不到一种组合满足条件。这个时候我们就手动把res改成0.

这不是有2个循环嵌套吗？怎么会是O(n)？

不是所有的两重循环嵌套都是O(n^2)！按照上面的算法流程分析下来，你会发现整个过程就让j向右移动了n，i向右移动了n（最坏情况），所有的while内的循环次数加起来不会超过n。所以实际上是2n，就是O(n)时间复杂度。

res = min(res, j - i + 1);

j-i+1就是目前这个窗口的长度。和之前的历史最短比较取最小。