JavaScript O(n) using flexible sliding window and prefix sums


  • 0

    The one-pass solution which has already been posted:

    var minSubArrayLen = function(s, nums) {
        let min = Infinity;
        for (let i = 0, j = 0, sum = 0; j < nums.length; j++) {
            sum += nums[j];
            while (sum >= s) {
                min = Math.min(min, j - i + 1);
                sum -= nums[i++];
            }
        }
        return min === Infinity ? 0 : min;
    };
    

    It may be easier to think about the sum step separately before improving to the above solution:

    var minSubArrayLen = function(s, nums) {
        const sums = [0];
        for (let k of nums) {
            sums.push(sums[sums.length - 1] + k);
        }
        let min = Infinity;
        for (let i = 0, j = 1; j < sums.length; j++) {
            while (sums[j] - sums[i] >= s) {
                min = Math.min(min, j - i);
                i++;
            }
        }
        return min === Infinity ? 0 : min;
    };
    

Log in to reply
 

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