美文网首页
Minimum Size Subarray Sum

Minimum Size Subarray Sum

作者: 极速魔法 | 来源:发表于2017-06-17 12:52 被阅读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;
    
    
    }
    

    相关文章

      网友评论

          本文标题: Minimum Size Subarray Sum

          本文链接:https://www.haomeiwen.com/subject/udnvqxtx.html