1 题目描述

209. 长度最小的子数组要求给定一个含有 n 个正整数的数组 nums 和一个正整数 target。任务是找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

2 解题思路

这个问题可以通过使用滑动窗口的方法来解决。滑动窗口是一个非常有效的技术，用于处理数组中的连续子数组问题。具体步骤如下：

1. 初始化两个指针 left 和 right，以及一个变量 sum 来记录当前子数组的和。
2. 使用 right 指针遍历数组，每次将 nums[right] 加入到 sum 中。
3. 当 sum 大于等于 target 时，更新子数组的长度，并尝试移动 left 指针以减少 sum 的值，直到 sum 小于 target。
4. 重复步骤 2 和 3 直到 right 到达数组末尾。

通过这种方法，我们可以在一次遍历中找到所有可能的子数组，并记录下最小的有效子数组长度。

3 Java 代码实现

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0; // 左指针
        int right = 0; // 右指针
        int sum = 0; // 当前窗口的总和
        int minLength = Integer.MAX_VALUE; // 初始化为最大值，表示最小长度
        
        for (; right < nums.length; right++) {
            sum += nums[right]; // 扩展窗口
            
            // 如果当前窗口的和大于等于目标值
            while (sum >= target) {
                int subLen = right - left + 1; // 当前子数组的长度
                minLength = Math.min(minLength, subLen); // 更新最短长度
                
                // 收缩窗口
                sum -= nums[left];
                left++;
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength; // 如果没有找到合适的子数组，返回 0
    }
}

• 时间复杂度: O(n)，其中 n 是数组 nums 的长度。每个元素最多被访问两次（一次增加窗口，一次减小窗口）。
• 空间复杂度: O(1)，只需要常数级别的额外空间。

4 注意事项

• 滑动窗口：使用滑动窗口技术，其中 left 指针和 right 指针分别定义窗口的开始和结束位置。
• 原地修改：直接在原数组上进行操作，不需要额外的空间。
• 最小窗口长度：记录并返回满足条件的最小窗口长度，如果不存在符合条件的子数组，返回 0。