给定一个含有 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
提示:
题目要求我们在数组中寻找和为target的最小子数组,我们可以先去想出暴力解法,然后再推算出滑动窗口的解法。
暴力法
我们需要找到最短的连续数组,那么最简单的方式就是用两个for循环去遍历数组累加数值,只要数值
≥
t
a
r
g
e
t
\ge target
≥target 就更新最小长度的状态。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ret = INT_MAX;
for(int left = 0; left < n; ++left)
{
int sum = 0;
for(int right = left; right < n; ++right)
{
sum += nums[right]; //累加数据
if(sum >= target)
{
ret = min(ret, right - left + 1); //更新状态
break; //已经找到了最小的长度,所以退出该层循环
}
}
}
return ret == INT_MAX ? 0 : ret;
}
};
时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
空间复杂度:
O
(
1
)
O(1)
O(1)
滑动窗口
滑动窗口的题目大抵都有一个固定的划分过程:
我们从暴力法中不难发现,其实当我们更新最小子数组长度时, l e f t + 1 → r i g h t left+1\to right left+1→right 的这段区间是重复遍历的,于是我们便可以使用滑动窗口来进行优化。当我们的 s u m ≥ t a r g e t sum \ge target sum≥target 时,同时更新 l e f t left left 的位置 与 最小子数组的长度,所谓的滑动窗口也是一种特殊的双指针类型,只不过两个指针的指向都是相同的方向。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int sum = 0, ret = INT_MAX;
for(int left = 0, right = 0; right < n; ++right)
{
sum += nums[right]; //进窗口
while(sum >= target) //判断
{
ret = min(ret, right-left+1); //更新状态
sum -= nums[left++]; //出窗口
}
}
return ret == INT_MAX ? 0 : ret; //返回结果
}
};
时间复杂度:
O
(
n
)
O(n)
O(n)
空间复杂度:
O
(
1
)
O(1)
O(1)