【LeetCode】209. 长度最小的子数组
1 题目描述
209. 长度最小的子数组要求给定一个含有 n 个正整数的数组 nums
和一个正整数 target
。任务是找出该数组中满足其总和大于等于 target
的长度最小的子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0。
2 解题思路
这个问题可以通过使用滑动窗口的方法来解决。滑动窗口是一个非常有效的技术,用于处理数组中的连续子数组问题。具体步骤如下:
- 初始化两个指针
left
和right
,以及一个变量sum
来记录当前子数组的和。 - 使用
right
指针遍历数组,每次将nums[right]
加入到sum
中。 - 当
sum
大于等于target
时,更新子数组的长度,并尝试移动left
指针以减少sum
的值,直到sum
小于target
。 - 重复步骤 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。