Slow! but try to implement most important propertise of Binary Search


  • 0
    R
    class Solution {
    public:
        int minSubArrayLen(int k, vector<int>& A) {
            int i,n,l,r;
            n=A.size();
            int sum[n+2];
            sum[0]=0;
            for(i=1;i<=n;i++)sum[i]=sum[i-1]+A[i-1];
            if(sum[n]<k)
              return 0;
            l=1,r=n;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                int f=0;
                for(i=1;i<=n-mid+1;i++){
                    if(sum[i+mid-1]-sum[i-1]>=k){
                        f=1;
                        break;
                    }
                }
                if(f==1)
                r=mid-1;
                else 
                l=mid+1;
                //cout<<f<<" "<<l<<" "<<r<<endl;
            }
            return l;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.