4ms O(n) Two pointers solution and 8ms O(nlogn) Binary search solution in C++


  • 3
    H
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            if (nums.empty()) return 0;
            int n = nums.size();
            
            //Two pointers solution, O(n)
            int sum = 0, j = 0, ans = 0;
            for (int i = 0 ; i < n ; i++) {
                sum += nums[i];
                while (sum - nums[j] >= s) { sum -= nums[j]; j++; }
                if (sum >= s) {
                    if (ans == 0 || i-j+1 < ans) ans = i-j+1;
                }
            }
    
            /*
            //Binary search solution, O(nlogn)
            //find min(j-i) s.t. sum[j] - sum[i] >= s
            //equivalently, given sum[i], find sum[j] >= sum[i] + s
            
            vector<int> sum(n+1, 0);
            for (int i = 0 ; i < n ; i++) sum[i+1] = sum[i] + nums[i];
            if (sum[n] < s) return 0;
            
            
            int ans = n;
            for (int i = 0 ; i < n ; i++) {
                int l = i+1, r = n;
                int target = sum[i] + s;
                if (target > sum[r]) break;
                if (target < sum[l]) return 1;
                while (l < r) {
                    int m = l + (r-l)/2;
                    if (sum[m] < target) l = m+1; else r = m;
                }
                if (l - i < ans) ans = l - i;
            }*/
            
            return ans;
        }
    };

Log in to reply
 

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