Leetcode 每日一题 209.长度最小的子数组
目录
问题描述
示例
算法分析
过题图片
O(n) 时间复杂度解法
算法步骤
代码实现
O(n log(n)) 时间复杂度解法
算法步骤
代码实现
题目链接
结论
问题描述
给定一个含有 n 个正整数的数组 nums 和一个正整数 target。任务是找出数组中和至少为 target 的最短子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例
-
输入：
target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组[4,3]是满足条件的最短子数组。 -
输入：
target = 4, nums = [1,4,4]输出：1解释：子数组[4]是满足条件的最短子数组。 -
输入：
target = 11, nums = [1,1,1,1,1,1,1,1]输出：0解释：不存在和至少为target的子数组。
算法分析
这个问题可以通过滑动窗口的方法来解决，时间复杂度为 O(n)。滑动窗口是一种常见的解决子数组问题的方法，它通过维护一个窗口来遍历数组，窗口内的元素和满足一定的条件。
过题图片
O(n) 时间复杂度解法
算法步骤
- 初始化两个指针
start和end，分别代表子数组的开始和结束位置，以及一个变量sum来存储当前窗口的和。 - 使用一个循环，通过移动
end指针来扩大窗口，直到窗口内的和大于等于target。 - 一旦找到满足条件的窗口，尝试通过移动
start指针来缩小窗口，同时更新最短长度max。 - 如果窗口的和小于
target，则继续移动end指针扩大窗口。 - 重复步骤 3 和 4，直到
end指针遍历完整个数组。 - 如果
max仍然是初始值，说明没有找到满足条件的子数组，返回 0；否则返回max。
代码实现
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int start = 0;
int end = 0;
int sum = 0;
int maxLen = Integer.MAX_VALUE;
while (end < nums.length) {
sum += nums[end];
while (start <= end && sum >= target) {
maxLen = Math.min(maxLen, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return maxLen == Integer.MAX_VALUE ? 0 : maxLen;
}
}O(n log(n)) 时间复杂度解法
对于进阶要求，我们可以利用二分查找来优化滑动窗口的缩小过程，从而将时间复杂度降低到 O(n log(n))。这种方法的核心思想是在满足条件的窗口内，使用二分查找来确定可以向左扩展的最远距离。
算法步骤
- 同 O(n) 解法的初始化。
- 使用一个循环，通过移动
end指针来扩大窗口，直到窗口内的和大于等于target。 - 使用二分查找在满足条件的窗口内找到最远的向左扩展距离。
- 更新最短长度
max。 - 重复步骤 3 和 4，直到
end指针遍历完整个数组。 - 返回
max的值。
代码实现
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int start = 0;
int end = 0;
int sum = 0;
int maxLen = Integer.MAX_VALUE;
while (end < nums.length) {
sum += nums[end];
while (start <= end && sum >= target) {
int len = end - start + 1;
if (len < maxLen) {
maxLen = len;
}
sum -= nums[start];
start++;
}
end++;
}
return maxLen == Integer.MAX_VALUE ? 0 : maxLen;
}
}题目链接
209. 长度最小的子数组 - 力扣（LeetCode）
结论
通过滑动窗口的方法，我们可以有效地解决寻找和至少为 target 的最短子数组问题。O(n) 的解法适用于大多数情况，而 O(n log(n)) 的解法则在某些特定情况下可以提供更好的性能。