209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl 1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
代码语言：javascript复制输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
代码语言：javascript复制输入：target = 4, nums = [1,4,4]
输出：1示例 3：
代码语言：javascript复制输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
进阶：
- 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
解法1：暴力解法：
暴力法是最直观的方法。初始化子数组的最小长度为无穷大，枚举数组 nums nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从nums[i] 到 nums[j] 的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是j−i 1）。 C 实现代码如下：
代码语言：javascript复制class Solution {
public:
// 暴力法解决
int minSubArrayLen(int target, vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int ans = INT_MAX;
for (int i = 0; i < nums.size(); i ) {
int sum = 0;
for (int j = i; j < nums.size(); j ) {
sum = nums[j];
if (sum >= target) {
ans = std::min(ans, j - i 1);
break;
}
}
}
return ans == INT_MAX ? 0 : ans;
}
};暴力解法的时间复杂度是O(n^2)，超时；空间复杂度为：O(1)
解法2：前缀和 二分查找
前缀和 二分查找的时间复杂度为：O(logn)，空间复杂度为O(n)
class Solution2 {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
vector<int> sums(n 1, 0);
// 为了方便计算，令 size = n 1
// sums[0] = 0 意味着前 0 个元素的前缀和为 0
// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
// 以此类推
// 计算nums数组的前缀和，注意前缀和数组的长度 = 原数组的长度nums.size() 1
for (int i = 1; i <= n; i ) {
sums[i] = sums[i - 1] nums[i - 1];
}
for (int i = 1; i <= n; i ) {
int target = s sums[i - 1];
auto bound = lower_bound(sums.begin(), sums.end(), target);
if (bound != sums.end()) {
ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
}
}
return ans == INT_MAX ? 0 : ans;
}
};解法3：滑动窗口解法：
滑动窗口时间复杂度为O(n)，空间复杂度为O(1)
C 实现
代码语言：javascript复制class Solution {
public:
// 滑动窗口解法
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
// end指针先去找右边，找到了再收缩左边，end继续去找到更优解，找到收缩左边。
int start = 0, end = 0;
int ans = INT_MAX;
// 终止指针指向窗口最右侧的位置索引
int sum = 0;
// end指针先去找右边
while (end < n) {
sum = nums[end];
// 收缩左侧窗口(找到了再收缩左边)
while (sum >= target) {
// 计算更新子数组的最小长度
ans = std::min(ans, end - start 1);
// 收缩左侧窗口
sum -= nums[start];
start ;
}
// end指针往右移动
end ;
}
return ans == INT_MAX ? 0 : ans;
}
};C#实现：
代码语言：javascript复制public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
if (nums.Length == 0) return 0;
int start = 0, end = 0;
int totalSum = 0;
int ans = int.MaxValue;
while (end < nums.Length)
{
totalSum = nums[end];
// 寻找到右侧的窗口终止位置后，收缩左侧窗口
while (totalSum >= target)
{
ans = Math.Min(ans, end - start 1);
totalSum -= nums[start];
start ;
}
end ;
}
return ans == int.MaxValue ? 0 : ans;
}
}
