给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
代码实现-暴力解法
int minSubArrayLen_brute(int s, vector<int>& nums) {
int n = nums.size(); // 获取数组长度
int min_len = n + 1; // 初始化最小长度为一个不可能的大值
for (int i = 0; i < n; i++) { // 外层循环遍历每个可能的起始位置
int sum = 0; // 重置当前子数组的和
for (int j = i; j < n; j++) { // 内层循环遍历从i开始的每个可能的结束位置
sum += nums[j]; // 累加当前元素到和中
if (sum >= s) { // 如果当前和达到或超过目标值
min_len = min(min_len, j - i + 1); // 更新最小长度
break; // 找到当前起始位置的最小子数组后提前退出内层循环
}
}
}
return (min_len == n + 1) ? 0 : min_len; // 如果没找到符合条件的子数组，返回0
}代码实现-滑动窗口（双指针）
#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int minSubArrayLen(int target, vector<int>& nums) {
int numsSize = nums.size();
int i = 0;
int minLen= INT_MAX;
int sum = 0;
for (int j = 0; j < numsSize;j++)
{
sum += nums[j];
while (sum>=target)
{
minLen = min(minLen, j - i + 1);
sum = sum - nums[i];
i++;
}
}
return minLen;
}
int main()
{
vector<int> array = { 1,2,3,4,5 };
int minLength = minSubArrayLen(4, array);
cout << minLength << endl;
system("pause");
return 0;
}
在 C++ 中，
INT_MAX是一个预定义的常量，表示当前系统中int类型所能表示的最大正整数值。它是标准库<climits>（C 语言中为<limits.h>）中定义的宏。
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
