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.

給一個數(shù)組和一個數(shù)尿扯，返回這個數(shù)組中和大于該數(shù)的連續(xù)子序列的最短長度粱玲。
最簡單的想法就是把所有情況都算一遍，復雜度是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;
    }
};

然后發(fā)現(xiàn)內(nèi)存溢出了凸主。然后想了想蚕钦，覺得自己做法有點傻沧卢，其實只要兩個指針向后移動就可以了讥脐。代碼如下：

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;
    }
};