209.长度最小的子数组
题目简介
给定一个含有 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
21class 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++) { // 设置子序列起点为i
sum = 0;
for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
sum += nums[j];
if (sum >= s) { // 一旦发现子序列和超过了s，更新result
subLength = j - i + 1; // 取子序列的长度
result = result < subLength ? result : subLength;
break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
}
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
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
23class 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)