LeetCode-209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input:          s = 7, nums = [2,3,1,2,4,3]                
Output: 2
Explanation: the subarray          [4,3]                 has the minimal length under the problem constraint.      

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

题目：给定一个数组Nums和s，寻找最短连续子序列，使得子序列的和不小于s。

思路：我自己做的时候的思路是，遍历数组，在第i个位置往后求和，如果sum>=s，则退出寻找并将ret与当前长度比较，ret取会更小的值。

代码：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
		int size = nums.size();
		if(accumulate(nums.begin(),nums.end(),0)<s) //两种特殊情况提前处理一下
			return 0;
        if(accumulate(nums.begin(),nums.end(),0)==s)
            return nums.size();
		int ret = nums.size();
		for(int i=0;i<size;i++){
			int j = i;
			int sum = 0;
			while(j<size){  //往后查找
                sum += nums[j];
                if(sum>=s){
                	ret = min(ret,j-i+1);
                    break;
                }
                j++;
			}
		}
		return ret;
    }
};
           

能通过，但只有AC 8%。

查看别人的解法，了解到了一种滑动窗口的概念 ，[l...r]这样的一个闭区间在数组上进行滑动，如果和小于s，则r向右扩展滑动，如果sum>s，l向右滑动。

代码如下：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
		int l=0,r=-1;
		int sum=0;
		int res = nums.size()+1;
		while(l<nums.size()){
			if(r+1<nums.size() && sum<s)
				sum += nums[++r];
			else
				sum -= nums[l++];	
			if(sum>=s)
				res = min(res,r-l+1);	
		}
		if(res == nums.size()+1)
			return 0;
		return res;
		}
};
           

这个算法是O(n)的，效率高多了。