力扣经典150题第三十题：长度最小的子数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣经典150题第三十题：长度最小的子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

力扣经典150题解析之三十：长度最小的子数组

1. 介绍

在本篇文章中，我们将解析力扣经典150题中的第三十题：长度最小的子数组。题目要求找出数组中满足其总和大于等于目标值 target 的长度最小的连续子数组，并返回其长度。

2. 问题描述

给定一个含有 n 个正整数的数组 nums 和一个正整数 target，找出该数组中满足其总和大于等于 target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

3. 示例

示例 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

4. 解题思路

方法一：滑动窗口

使用滑动窗口技巧，维护窗口的左右边界 left 和 right，以及窗口内元素的和 sum。初始化时，left 和 right 都指向数组的起始位置，sum 初始化为0。

将 right 右移，扩展窗口，将 nums[right] 加入窗口的和 sum 中。
当 sum 大于等于 target 时，更新最小长度，并尝试将 left 右移，缩小窗口，直到 sum 小于 target。
遍历整个数组完成后，即可得到最小长度的连续子数组。

5. 算法实现

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int left = 0, sum = 0;
    int minLength = Integer.MAX_VALUE;

    for (int right = 0; right < n; right++) {
        sum += nums[right];
        
        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left++];
        }
    }
    
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}