Concise JavaScript O(n) solution using prefix sums


  • 0
    var maxSubArrayLen = function(nums, k) {
        const presums = new Map([[0, 0]]);
        let res = 0;
        for (let sum = nums[0], i = 0; i < nums.length; sum += nums[++i]) {
            if (presums.has(sum - k)) {
                res = Math.max(res, i + 1 - presums.get(sum - k));
            }
            if (!presums.has(sum)) presums.set(sum, i + 1);
        }
        return res;
    };
    
    1. Remember the left-most index at which accumulated sums occur.
    2. If we can subtract one of those sums from the most recent sum to get k, we have found a subarray of size current_index - sum_index.

Log in to reply
 

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