[LeetCode] 209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

长度最小的子数组。

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

还是 sliding window 的思路做。给两个指针 left 和 right，也用一个变量 sum 记录遍历到的数字们的加和。遍历的时候一开始也是只移动右指针，当 sum >= target 的时候，开始试图移动左指针。所谓的最短的子数组也就是左右指针的距离最短，所以每次当 sum >= target 的时候，需要记录 right - left 的值。注意有可能最后是找不到一个子数组满足其 sum >= target 的，如果是这种情况，需要输出 0。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        while (end < nums.length) {
            sum += nums[end];
            end++;
            while (sum >= target) {
                res = Math.min(res, end - start);
                sum -= nums[start];
                start++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

JavaScript实现

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    let left = 0;
    let right = 0;
    let sum = 0;
    let res = Number.MAX_SAFE_INTEGER;
    while (right < nums.length) {
        sum += nums[right];
        right++;
        while (sum >= target) {
            res = Math.min(res, right - left);
            sum -= nums[left];
            left++;
        }
    }
    return res === Number.MAX_SAFE_INTEGER ? 0 : res;
};