【LeetCode】209. 长度最小的子数组

in #programming4 months ago

1 题目描述

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

2 解题思路

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

  1. 初始化两个指针 leftright,以及一个变量 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。