Minimum Size Subarray Sum

2017-06-17  本文已影响2人  极速魔法

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.

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        assert(s>0);
        //[i...j]
        int i=0,j=-1;
        int sum=0;
        int res=nums.size()+1;


        while(i<nums.size()){
            // i<nums.size()) && (j+1<nums.size())maybe j to end,
            // "||" may i to somewhere,j out of end
            //i not
            if(j+1<nums.size() && sum<s){
                j++;
                sum+=nums[j];
            } else{
                sum-=nums[i];
                i++;

            }
            //i add judge sum
            if(sum>=s){
                res=min(res,j-i+1);
            }

        }

        if(res==nums.size()+1){
            return 0;
        }
        return res;
    }
};

int main(){
    int arr[]={2,3,1,2,4,3};
    vector<int> val(arr,arr+sizeof(arr)/sizeof(int));

    int s=7;

    int ret=Solution().minSubArrayLen(s,val);
    cout<<ret<<endl;


}
上一篇下一篇

猜你喜欢

热点阅读