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.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

给一个数组和一个数，返回这个数组中和大于该数的连续子序列的最短长度。
最简单的想法就是把所有情况都算一遍，复杂度是O(n^2)。

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

然后发现内存溢出了。然后想了想，觉得自己做法有点傻，其实只要两个指针向后移动就可以了。代码如下：

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

看了下大神的简洁写法，感觉自己的码代码能力真是弱爆了！

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size(), start = 0, sum = 0, minlen = INT_MAX;
        for (int i = 0; i < n; i++) { 
            sum += nums[i]; 
            while (sum >= s) {
                minlen = min(minlen, i - start + 1);
                sum -= nums[start++];
            }
        }
        return minlen == INT_MAX ? 0 : minlen;
    }
};