11--209. 长度最小的子数组-526互联

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

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

【暴力解法超时】

【双重for循环代码如下：】

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;    //这行代码将 min 初始化为整型的最大值，以确保
                                        //任何比这个值小的子数组长度都可以成为 min 的初始值
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum >= target) {
                return 1;
            } 

            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];

                if (sum >= target) {
                    min = Math.min(min, j - i + 1);//这行代码用于更新 min 的值。在每次找到一个满足条件的子数组时，
                         //它会计算当前子数组的长度 j - i + 1，并与当前的 min 值进行比较，取较小的值作为新的 min 值
                    break;
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

【滑动窗口（实际上是队列相加）】

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //l = low, h = high, sum用来记录滑动窗口的总值
        //h用来滑动（或者说h用来入队，l用来出队）
        int l = 0, h = 0, sum = 0;
        int min = Integer.MAX_VALUE;
        while (h < nums.length) {
             sum += nums[h];
             h++;
             while (sum >= target) {
                 min = Math.min(min, h - l); //因为是先加的，h又移动的，所以直接h-l，不用再＋1
                 sum -= nums[l];    //出队
                 l++;
             }
        }
        return min == Integer.MAX_VALUE ? 0 : min;  
    }
}