209.长度最小的子数组

题目链接

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

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

示例1：

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

示例2：

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

示例3:

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

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

滑动窗口

定义开始和结束指针start、end均为0，子数组的和为sum，最终结果即子数组元素最小值min置为无穷大

在end小于数组长度的情况下执行循环，将end指向的元素累加到sum，如果此时的sum>=target，min取当前子数组长度和min中暂存的最小值中小的那个，end的右移暂停，start开始右移，并在sum中减去start指向的那个元素。

最后注意判断不存在这样的子数组的情况

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length; // 数组长度
        int start = 0; // 起始指针
        int end = 0; // 终止指针
        int sum = 0; // 子数组的和
        int min = Integer.MAX_VALUE; // 置子数组最小长度为无穷大
        // end可以右移至数组最后一个元素结束循环
        while (end < length){
            // 每一次end右移都改变子数组和
            sum += nums[end];
            while (sum >= target){
                min = Math.min(min, end - start + 1); //在子数组和大于target的条件下，子数组长度最小值计算
                sum -= nums[start];
                start++;

            }
            end++;
        }
        if(min == Integer.MAX_VALUE){
            return 0;
        }
        return min;
    }
}