209. 长度最小的子数组
209. 长度最小的子数组
🟠 🔖 数组
二分查找
前缀和
滑动窗口
🔗 力扣
LeetCode
题目
Given an array of positive integers nums
and a positive integer target
, return the minimal length of a __subarray whose sum is greater than or equal to target
. If there is no such subarray, return 0
instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
Follow up: If you have figured out the O(n)
solution, try coding another solution of which the time complexity is O(n log(n))
.
题目大意
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 子数组 ,并返回其长度。如果不存在符合条件的子数组,返回 0
。
子数组是数组中连续的非空元素序列。
解题思路
思路一:滑动窗口
- 初始化变量:使用两个指针(或滑动窗口)来遍历数组;
- 扩大窗口:移动右指针,向右扩大求和;
- 缩小窗口:一旦窗口总和大于等于
target
,就移动左指针缩小窗口; - 更新最小长度:过程中更新最小长度;
复杂度分析
- 时间复杂度:
O(n)
,其中 n 是数组的长度; - 空间复杂度:
O(1)
思路二:暴力查找
- 初始化子数组的最小长度为无穷大;
- 枚举数组
nums
中的每个下标作为子数组的开始下标; - 对于每个开始下标
i
,需要找到大于或等于i
的最小下标j
,使得从nums[i]
到nums[j]
的元素和大于或等于s
; - 更新子数组的最小长度(此时子数组的长度是
j−i+1
);
复杂度分析
- 时间复杂度:
O(n^2)
,需要遍历每个下标作为子数组的开始下标,对于每个开始下标,需要遍历其后面的下标; - 空间复杂度:
O(1)
思路三:二分查找
- 暴力查找的时间复杂度是
O(n^2)
,因为在确定每个子数组的开始下标后,找到长度最小的子数组需要O(n)
的时间。如果使用二分查找,则可以将时间优化到O(logn)
。 - 为了使用二分查找,需要额外创建一个数组 sums 用于存储数组 nums 的前缀和,其中
sums[i]
表示从nums[0]
到nums[i−1]
的元素和。 - 得到前缀和之后,对于每个开始下标
i
,可通过二分查找得到大于或等于i
的最小下标bound
,使得sums[bound]−sums[i−1]≥s
,并更新子数组的最小长度(此时子数组的长度是bound−(i−1)
)。
因为这道题保证了数组中每个元素都为正,所以前缀和一定是递增的,这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正,这里就不能使用二分来查找这个位置了。
复杂度分析
时间复杂度:
O(nlogn)
,遍历每个下标的时间复杂度是O(n)
,二分查找的时间复杂度是O(logn)
,因此总时间复杂度是O(nlogn)
。空间复杂度:
O(n)
,额外创建数组sums
存储前缀和。
代码
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
let left = 0,
sum = 0,
minLength = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength == Infinity ? 0 : minLength;
};
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
let n = nums.length,
res = Infinity;
if (n == 0) return 0;
for (let i = 0; i < n; i++) {
let sum = 0;
for (let j = i; j < n; j++) {
sum += nums[j];
if (sum >= target) {
res = Math.min(res, j - i + 1);
break;
}
}
}
return res == Infinity ? 0 : res;
};
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var minSubArrayLen = function (target, nums) {
let n = nums.length,
sum = [0],
res = Infinity;
for (let i = 1; i <= n; i++) {
sum[i] = nums[i - 1] + sum[i - 1];
}
for (let i = 1; i <= n; i++) {
let newTarget = target + sum[i - 1];
let bound = binarySearch(sum, newTarget, i, n);
if (bound != -1) {
res = Math.min(res, bound - i + 1);
}
}
return res == Infinity ? 0 : res;
};
var binarySearch = function (arr, target, l, r) {
if (arr[r] < target) return -1;
while (l < r) {
let mid = (l + r) >> 1;
if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
return arr[l] >= target ? l : -1;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
76 | 最小覆盖子串 | [✓] | 哈希表 字符串 滑动窗口 | |
325 | 和等于 k 的最长子数组长度 🔒 | 数组 哈希表 前缀和 | ||
718 | 最长重复子数组 | 数组 二分查找 动态规划 3+ | ||
1658 | 将 x 减到 0 的最小操作数 | 数组 哈希表 二分查找 2+ | ||
2090 | 半径为 k 的子数组平均值 | 数组 滑动窗口 | ||
2233 | K 次增加后的最大乘积 | 贪心 数组 堆(优先队列) | ||
3095 | 或值至少 K 的最短子数组 I | 位运算 数组 滑动窗口 |