算法1:暴力枚举
枚举出所有和大于等于target的数组,然后求出其中长度最小的那一个
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 记录结果
int ret = INT_MAX;
int n = nums.size();
// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
// 由于是取到最⼩,因此枚举的过程中要尽量让数组的⻓度最⼩
// 枚举开始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 记录从这个位置开始的连续数组的和
// 寻找结束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 将当前位置加上
if (sum >= target) // 当这段区间内的和满⾜条件时
{
// 更新结果,start 开头的最短区间已经找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后结果
return ret == INT_MAX ? 0 : ret;
}
};
算法2:滑动窗口
从数组的起始位置开始,我们每一次+=上当前位置的nums[i],然后判断当前的总和是否满足条件。如果满足就让左边的数字出窗口,然后窗口变小;如果当前的总和不满足,继续让窗口变大
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//看到这道题典型的使用滑动窗口
int left = 0, right = 0;
int len = INT_MAX;
int sum = 0;
while(right < nums.size())
{
sum += nums[right];
while(sum >= target)
{
len = min(len, right - left + 1);
//左边的数字出窗口
sum -= nums[left++];
}
right++;
}
if(len == INT_MAX)return 0;
return len;
}
};
为什么要使用滑动窗口?因为我们看到这道题的要求就是需要一段区间的数值,然后这个区间的的大小一直是不知道的,每次取的是区间右边的第一个数字,不要的是区间左边的第一个数字,并且区间一旦不满足左边的第一个数字也就是不需要了。所以说就是需要滑动窗口来解决这种问题