C++ O(N) and O(NlogN), very very clear


  • 0
    X
    class Solution {
    public:
        //O(NlogN)  binary search
        int minSubArrayLen(int s, vector<int>& nums) {
            if(nums.empty()){
               return 0;
            }
            int size = nums.size();
            vector<int> sum(size, 0);
            sum[0] = nums[0];
            for(int i = 1; i < size; ++i){
                sum[i] = sum[i - 1] + nums[i];
            }
            int minlen = INT_MAX;
            for(int i = 0; i < size; ++i){
                int p = lower_bound(sum[i] + s - nums[i], i, size, sum);
                if(p != size){
                    minlen = min(minlen, p - i + 1);
                }else{
                    break;
                }
            }
            return minlen == INT_MAX ? 0 : minlen;
        }
        int lower_bound(int x, int left, int right, vector<int>& sum){
            while(left < right){
                int mid = left + (right - left) / 2;
                if(sum[mid] < x){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
            return left;
        }
        /* O(N) two pointers
        int minSubArrayLen(int s, vector<int>& nums) {
           if(nums.empty()){
               return 0;
           }
           int size = nums.size();
           int i = 0,j = 0;
           int sum = 0;
           int minlen = INT_MAX;
           while(j < size){
               while(j < size && sum < s){
                   sum += nums[j];
                   ++j;
               }
               if(sum < s){
                   break;
               }
               while(i < j && sum >= s){
                   sum -=nums[i];
                   ++i;
               }
               minlen = min(minlen, j - i + 1);
           }
           return minlen == INT_MAX ? 0 : minlen;
        }
        */
    };
    

    by the way, the upper_bound is ( which is not related to this problem, I just share ):

    int upper_bound(int x, int left, int right, vector<int>& sum){
                while(left < right){
                    int mid = left + (right - left) / 2;
                    if(sum[mid] <= x){
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                return left;
     }

Log in to reply
 

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