长度最小的子数组
难度:
标签:
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 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
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
代码结果
运行时间: 29 ms, 内存: 26.2 MB
/*
* 思路：
* 使用Java Stream API来处理数组。首先将数组转换为Stream，然后使用Stream的特性来找到最短的子数组。
* 我们不能直接使用Stream来实现滑动窗口，所以这里先计算出每个前缀和，然后再寻找符合条件的子数组长度。
*/
import java.util.Arrays;
import java.util.OptionalInt;
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int[] prefixSums = new int[n + 1];
for (int i = 0; i < n; i++) {
prefixSums[i + 1] = prefixSums[i] + nums[i];
}
OptionalInt minLength = Arrays.stream(prefixSums).boxed()
.flatMap(i -> Arrays.stream(prefixSums)
.skip(i + 1)
.filter(j -> j - i >= target)
.map(j -> j - i))
.min(Integer::compareTo);
return minLength.isPresent() ? minLength.getAsInt() : 0;
}
}解释
方法:
该题解使用双指针滑动窗口的思路来解决问题。通过左右两个指针构成一个窗口，右指针不断向右移动扩大窗口，累加窗口内的元素总和，当总和大于等于目标值时，开始收缩窗口，移动左指针缩小窗口，并更新最小子数组长度，直到窗口内的总和小于目标值，然后继续扩大窗口，重复上述过程，直到右指针到达数组末尾。最终返回找到的最小子数组长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在累积总和大于等于目标值后，需要通过移动左指针来缩小窗口？这样做的目的是什么？
▷🦆
在题解中提到，当总和大于等于目标值时，会尝试更新最小子数组长度。如果存在多个长度相同的子数组满足条件，这种方法是否能保证找到所有这样的子数组？
▷🦆
题解中提到，如果最小子数组长度为无穷大，则返回0。这种情况是如何判断的？在什么情况下，最小子数组长度会保持为无穷大？
▷🦆
在初始化最小子数组长度为无穷大时，使用了`float('inf')`。使用这种方法有什么特别的考虑吗，比如在某些编程环境下有可能不支持这种表示吗？
▷相关问题
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 105s和t由英文字母组成
进阶：你能设计一个在
o(m+n) 时间内解决此问题的算法吗？