`

LintCode - Minimum Size Subarray Sum

阅读更多

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

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.

Challenge

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

int minimumSize(vector<int> &nums, int s) {
    int n = nums.size();
    int minLen = n+1;
    int sum = 0;
    int left = 0;
    for(int i=0; i<n; i++) {
        sum += nums[i];
        while(sum >= s) {
            int len = i-left+1;
            minLen = min(minLen, len);
            sum -= nums[left++];
        }
    }
    return minLen>n ? 0 : minLen;
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics