题目简介
题目链接
给定一个含有 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] <= 104
进阶：
如果你已经实现 O (n) 时间复杂度的解法，请尝试设计一个 O (n log (n))
时间复杂度的解法。
思路
首先想到的会是暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
int subLength = 0;
for (int i = 0; i < nums.size(); i++) {
sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
break;
}
}
}
return result == INT32_MAX ? 0 : result;
}
};
|
就是从每个开始的位置开始，向后枚举，直到找到符合条件的子序列
如何优化到使用一个 for 循环呢？我们可以使用双指针法，或者在这道题里可以叫做滑动窗口法
现在只有一个 for 循环，该记录窗口的起始位置还是结束位置呢？答案是结束位置，因为如果是起始位置的话依然会陷入需要枚举结束位置的困境，那样还是 O (n^2) 的复杂度
所以我们循环的索引就设置为结束位置，然后把起始位置先设置为 0，然后每次发现窗口内的序列和超过了 s，就要把起始位置向后移动来减小窗口的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i=0;
int sum=0;
int subLength=0;
int result=INT_MAX;
for(int j=0;j<nums.size();j++){
sum+=nums[j];
while(sum>=target){
subLength=j-i+1;
if(subLength<result){
result=subLength;
}
sum-=nums[i];
i++;
}
}
if(result==INT_MAX)return 0;
return result;
}
};
|
因为每个元素最多只会被遍历两次（一进一出），所以时间复杂度是O(n)，空间复杂度是O(1)