给定一个含有 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
- 如果你已经实现
O(n)
时间复杂度的解法, 请尝试设计一个O(n log(n))
时间复杂度的解法。
解法一:
class Solution {
public:
// 寻找最短子数组长度,其总和不小于目标值
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(); // 获取数组的长度
if (n == 0) // 如果数组为空,则直接返回0
return 0;
int ans = INT_MAX; // 初始化最短子数组长度为最大整数
vector<int> sums(n + 1, 0); // 创建一个大小为n+1的数组,用于存储前i个元素的和
// 计算前i个元素的和
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
// 遍历每个位置,查找以当前位置开始的满足条件的子数组
for (int i = 1; i <= n; i++) {
// 计算当前位置及之前元素的和加上目标值
int s = sums[i - 1] + target;
// 使用lower_bound在sums数组中查找大于等于s的第一个元素的位置
auto bound = lower_bound(sums.begin(), sums.end(), s);
// 如果找到这样的位置,更新最短子数组长度
if (bound != sums.end()) {
ans = min(ans, static_cast<int>(bound - sums.begin()) - i + 1);
}
}
// 如果最短子数组长度没有改变,则返回0,表示找不到符合条件的子数组
return ans == INT_MAX ? 0 : ans;
}
};
解法思路:
- 首先判断输入的数组是否为空,如果为空,则直接返回0。
- 定义一个变量ans,用于存储最小子数组的长度。初始值设为INT_MAX,表示一个无穷大的值。
- 定义一个长度为n+1的数组sums,用于存储nums数组的前缀和。sums[i]表示nums数组中前i个元素的和。
- 遍历nums数组,计算sums数组的前缀和。
- 遍历nums数组,对于每个元素nums[i],计算目标和s=sums[i-1]+target。
- 使用lower_bound函数在sums数组中查找大于等于s的元素的位置,得到指向该位置的迭代器bound。
- 如果找到了这样的位置,则计算子数组的长度ans,并更新ans的最小值。
- 返回ans的值,如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0。
解法二:窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(); // 数组长度
if (n == 0) // 如果数组为空,直接返回0
return 0;
int ans = INT_MAX; // 最小子数组长度,初始值设为INT_MAX,表示一个无穷大的值
int sum = 0, start = 0; // 子数组的和sum和起始位置start
// 遍历数组
for (int end = 0; end < n; end++) {
sum += nums[end]; // 计算当前子数组的和
// 如果子数组的和sum大于等于目标值target,进入循环
while (sum >= target) {
ans = min(ans, end - start + 1); // 更新最小子数组长度
sum -= nums[start]; // 从子数组中减去起始位置元素的值
start++; // 起始位置向右移动一位,相当于缩短了子数组的长度
}
}
return ans == INT_MAX ? 0 : ans; // 返回最小子数组长度,如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0
}
};
这个窗口的解题思路是通过两个指针start和end来构建一个滑动窗口,窗口的左边界是start,右边界是end。初始时,start和end都指向数组的第一个元素。
在遍历数组的过程中,不断移动end指针,将当前元素加入窗口的和sum中。如果sum大于等于目标值target,则进入循环。
在循环中,先计算当前子数组的长度(end - start + 1),并将其与之前的最小子数组长度ans进行比较,保留较小的值。接着,从窗口中减去起始位置元素的值,即sum -= nums[start],然后将start指针向右移动一位,相当于缩短了窗口的长度。
接着再次判断sum是否大于等于target,并重复上述过程,直到窗口中的和sum小于目标值target。然后继续移动end指针,将下一个元素加入窗口,并再次重复上述过程。
最终,当整个数组遍历完毕后,返回最小子数组长度ans。如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0。
标签:target,nums,209,sum,C++,力扣,数组,ans,长度 From: https://blog.csdn.net/2301_80345285/article/details/140633337