Evolve from brute force to optimal


  • 0
    1. O(n^3), compute the sum of all sub arrays.
        int minSubArrayLen(int s, vector<int>& nums) {
            int n = nums.size(), len = n+1;
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++) {
                    int sum = 0;
                    for(int k=i;k<=j;k++) sum+=nums[k];
                    if(sum>=s) {
                        len = min(len,j-i+1);
                        break;
                    }
                }
            return len==n+1? 0:len;
        }
    
    1. O(n^2), compute the sum of a sub array can be improved to constant by computing prefix sum.
        int minSubArrayLen(int s, vector<int>& nums) {
            int n = nums.size(), len = n+1;
            vector<int> pre(n);
            for(int i=1;i<n;i++) pre[i]=pre[i-1]+nums[i-1];
            for(int i=0;i<n;i++)
                for(int j=i;j<n;j++) {
                    int sum = pre[j]-pre[i]+nums[j];
                    if(sum>=s) {
                        len = min(len,j-i+1);
                        break;
                    }
                }
            return len==n+1? 0:len;
        }
    
    1. O(nlogn) The prefix sum array is increasing so we can do binary search.
        int minSubArrayLen(int s, vector<int>& nums) {
            if(nums.empty()) return 0;
            int n = nums.size(), len = n+1;
            vector<int> pre(n);
            pre[0]=nums[0];
            for(int i=1;i<n;i++) pre[i]=pre[i-1]+nums[i];
            for(auto i = pre.begin(); i!=pre.end();i++) {
                auto j = lower_bound(i,pre.end(),*i+s-nums[i-pre.begin()]);
                if(j!= pre.end()) len = min(len,int(j-i)+1);
            }
            return len==n+1? 0:len;
        }
    
    1. O(n) Two pointers.
        int minSubArrayLen(int s, vector<int>& nums) {
            int l=0,r=0, sum=0, n = nums.size(), len=n+1;
            while(r < n) {
                sum+=nums[r++];
                if(sum<s) continue;
                while(sum>=s) sum-=nums[l++];
                len = min(len, r-l+1);
            }
            return len == n+1 ? 0:len;
        } 
    

Log in to reply
 

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