[LeetCode]Minimum Size Subarray Sum

双指针题，两个指针i，j，j先一直移直到sum大于给定数s，然后移动i缩小区间直到sum小于s，然后j - i + 1就是我们要找的长度，双指针移动过程中这个数的最大值就是答案。首先对于一个数组里的元素k，指针j有两种情况：

• 不停下经过k
• 从0开始不停下经过k，说明不存在以k结尾的subarray sum大于s
• 在i停下之后再移动j后经过k，说明加上k的区间和依然小于s，那么以k结尾的和大于s的区间长度一定大于之前找到的区间长度(j移动到k至少移动了一位)。
• 停在k，那么我们找的就是一k结尾的区间和大于s的最小区间长度。

所以算法是正确的，时间复杂度O(n)，代码如下：

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

view raw Minimum Size Subarray Sum.cpp hosted with ❤ by GitHub