209 长度最小的子数组
滑动窗口解法
需要强调的是,题目说了 nums 数组中的元素都是正数,有了这个前提才能使用滑动窗口算法,因为窗口扩大时窗口内元素之和必然增大,窗口缩小时窗口内元素之和必然减小。
如果 nums 数组中包含负数,则窗口扩大时元素和不见得就增大,窗口缩小时元素和不见得就减小,这种情况就不能单纯使用滑动窗口技巧了,可能需要混合动态规划和单调队列来做。
暴力做法(不能通过)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX;
for(int i = 0; i < nums.size(); i++){
int sum = 0;
for(int j = i; j < nums.size(); j++){
sum += nums[j];
if(sum >= target)
len = min(len, j - i + 1);
}
}
return len == INT_MAX ? 0 : len;
}
};
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(1)\)
双指针法
class Solution {
public:
const int INF = 0x3f3f3f3f;
int minSubArrayLen(int target, vector<int>& nums) {
int leftIndex = 0;
int len = INF;
int sum = 0;
// 移动滑动窗口出口
for(int rightIndex = leftIndex; rightIndex < nums.size(); rightIndex++){
sum += nums[rightIndex];
// 移动滑动窗口入口
while(sum >= target){
len = min(len, rightIndex - leftIndex + 1);
// 关键步骤,不要忘记!
sum -= nums[leftIndex];
leftIndex++;
}
}
return len == INF ? 0 : len;
}
};
时间复杂度:O(n)
- rightIndex移动了n次,leftIndex移动了n次,共移动2n次
空间复杂度:O(1)
以前写的版本
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
题目关键在于:这个子数组是连续的
解法一:暴力枚举
先枚举子数组的起点,再往后枚举,满足sum >= target停止,计算子数组长度 j - i + 1
class Solution {
private:
const int INF = 0x3f3f3f3f;
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ans = INF;
for(int i = 0; i < n; i++){
int sum = 0;
for(int j = i; j < n; j++){
sum += nums[j];
if(sum >= target)
ans = min(ans, j - i + 1);
}
}
if(ans == INF)
return 0;
else
return ans;
}
};
复杂度分析
时间复杂度:\(O(n^2)\),其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标,对于每个开始下标,需要遍历其后面的下标得到长度最小的子数组。
空间复杂度:O(1)。
解法二: 前缀和 + 二分查找
解法一枚举起点之后又向后枚举了n个元素才找到sum >= target
由于本题限定了“正整数元素”,对于这种找到第一个满足sum >= target的元素,显然可以使用二分查找
我们的目标是sum >= target 而不是num >= target,因此需要一个数组记录每个元素作为末尾时的sum[i]
因此想到前缀和
class Solution {
private:
const int INF = 0x3f3f3f3f;
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> s(n + 1);
// 计算前缀和
for (int i = 1; i <= n; i++) {
// 这里原本是nums[i],但是nums和s的下标之间偏移了1
s[i] = s[i - 1] + nums[i - 1];
}
int ans = INF;
// 遍历起点,由于是遍历前缀和,所以下标可直接从1开始
for (int i = 1; i <= n; i++) {
// 我们要找到sum >= target
// sum = s[idx] - s[i - 1]
// 因此二分查找的目标为在数组s中找到大于等于target + s[i -
// 1]的第一个元素
int t = target + s[i - 1];
auto it = lower_bound(s.begin(), s.end(), t);
if (it != s.end()) {
int idx = distance(s.begin(), it);
ans = min(ans, idx - i + 1);
}
}
return ans == INF ? 0 : ans;
}
};
二分自己实现如下:
class Solution {
private:
const int INF = 0x3f3f3f3f;
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> s(n + 1);
// 计算前缀和
for (int i = 1; i <= n; i++) {
// 这里原本是nums[i],但是nums和s的下标之间偏移了1
s[i] = s[i - 1] + nums[i - 1];
}
int ans = INF;
// 遍历起点,由于是遍历前缀和,所以下标可直接从1开始
for (int i = 1; i <= n; i++) {
// 我们要找到sum >= target
// sum = s[idx] - s[i - 1]
// 因此二分查找的目标为在数组s中找到大于等于target + s[i - 1]的第一个元素
int t = target + s[i - 1];
int l = i, r = n;
while(l < r){
int mid = l + r >> 1;
if(s[mid] >= t) r = mid;
else l = mid + 1;
}
if(s[l] >= t)
ans = min(ans, l - i + 1);
}
return ans == INF ? 0 : ans;
}
};
解法三:移动窗口
由于题目的子数组是连续的序列,求sum >= target子数组长度最小值,实际上是要求子数组滑动时的最小值 >= target
想让子数组长度最小,意味着这个移动窗口的长度不定,因此移动窗口的头部也需要改变
加进一个元素
class Solution {
private:
const int INF = 0x3f3f3f3f;
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int start = 0, end = 0;
int ans = INF;
int sum = 0;
while(end < n){
sum += nums[end];
while(sum >= target){
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INF ? 0 : ans;
}
};
以上是双指针做法
如果套模板,使用队列解决,则是:
class Solution {
private:
const int INF = 0x3f3f3f3f;
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
queue<int> q;
int sum = 0;
int ans = INF;
for(int i = 0; i < n; i++){
// 先加nums[i] 再对队头进行判断
q.push(i);
sum += nums[i];
// 处理队头
while(!q.empty() && sum >= target){
sum -= nums[q.front()];
ans = min(ans, q.back() - q.front() + 1);
q.pop();
}
}
return ans == INF ? 0 : ans;
}
};
需要注意的是,队列的头是早加入的元素,尾是刚刚加入的元素,即头对应start,尾对应end