7 line C++ O(n) solution


  • 0
    F

    Not sure this has been proposed so far. The basic idea is to use two pointers.

    • The fast one goes first, until the interval sum >= s
    • The slow one goes slowly, until the interval sum < s
    • Then, fast - slow + 1 is the length of current minimal interval that sum >= s
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int slow = 0, fast = 0, n = nums.size(), sum = 0, maxLength = n + 1;
            while (fast < n){
                while (fast < n && sum < s) sum += nums[fast++];
                while (slow < fast && sum >= s) sum -= nums[slow++];
                maxLength = min(maxLength, fast - slow + 1);
            }
            return maxLength == n + 1 ? 0 : maxLength;
        }
    };
    

Log in to reply
 

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