My C++ moving window solution, O(n) time, O(1) space; another binary search version added(O(nlogn) time)


  • 5
    D
    1. O(n) time, O(1) space moving window method
      using a moving window [start,end] to calculate the sum, first move end forward to get a sub-array with sum>=s, then move start forward to make sum < s, then move end again,..., until end reach the end of array.
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int start=0, end=0, sum=0, len = nums.size(), res;
            while(end<len)
            {
                while(sum<s && end<len) sum += nums[end++];
                while(sum>=s) sum -=nums[start++];
                res = min(res, end-start + 1);
            }
            return res>len?0:res;
        }
    };
    
    1. O(nlogn) time, O(n) space version, binary search method
    class Solution {
    public:
        int binary_search(vector<int>&sum, int left, int target)
        {
            int right = sum.size()-1, mid;
            while(left<=right)
            {
                mid = (left+right)>>1;
                if(sum[mid]>=target) right = mid-1;
                else left = mid+1;
            }
            return (left<sum.size()?left:-1);
        }
        
        int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        vector<int> sum(len+1,0);
        int i, start = 0, end;
        int res = len+1;
        
        if(len>0)
        {
            for(i=1;i<=len;i++) sum[i] =sum[i-1] + nums[i-1];
            while(start<len && (end = binary_search(sum, start+1, s+sum[start]))>=0 )
            {
                res = min(res, end-start);
                start++;
            }
        }
        return res>len?0:res;

  • 1
    Z

    For the case [1,2] and s=4, the o(n) method doesn't work.

    while(sum<s && end<len) sum +=nums[++end];//It will be out of range.


  • 0
    D

    Thanks for pointing this out and it is fixed in the updated version. Appreciate your comments.


Log in to reply
 

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