An intuitive solution in C, accepted as best O(n) time complexity


  • 0
    //AC - 0ms;
    int minSubArrayLen(int s, int* nums, int size)
    {
        int l=0, r=0; //l pointing to the first element of the subarray while the r pointing to the next element;
        int sum = 0;
        while(r < size) //initialize the l and r pointers;
        {
            sum += nums[r++];
            if(sum >= s) break;
        }
        if(sum < s) return 0; //there is no such sum that can be equal to or greater than s;
        int min = r-l;
        while(r <=size)
        {
            if(r < size) sum += nums[r++];
            while(sum-nums[l]>=s && l<r)  sum -= nums[l++];
            if(sum < s) sum += nums[--l]; //only when the current sum is less, add the last left-most element to ensure its validity;
            if(r-l < min) min = r-l;
            if(r == size) return min;
        }
    }

Log in to reply
 

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