算法 —— 滑动窗口

简介: 算法 —— 滑动窗口

sum比target小就进窗口,sum比target大就出窗口,由于数组是正数,所以相加会使sum变大,相减会使sum变小,至于为什么可以这样做,这其实是在暴力枚举的基础上进行了优化,例如2,3,1,2相加等于8已经超过target,这样就不需要继续加后面的4,3,因为此时已经满足条件,我们要做的是在满足要求的基础上使len尽量小。

代码实现如下:

class Solution {
public:
int minSubArrayLen(int target, vector& nums) {
int sum = 0, len = INT_MAX, n = nums.size();
for (int right = 0, left = 0; right < n; right++)
{
sum += nums[right]; // 进窗口
while (sum >= target) // 判断
{
len = min(len, right - left + 1); // 更新结果
sum -= nums[left++]; // 出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};

相关文章
|
1月前
|
算法
【算法】滑动窗口——最大连续1的个数
【算法】滑动窗口——最大连续1的个数
|
4月前
|
算法 测试技术 C++
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
|
4月前
|
机器学习/深度学习 算法
【优选算法】—— 滑动窗口类问题
【优选算法】—— 滑动窗口类问题
|
1月前
|
算法
【算法】滑动窗口——最小覆盖子串
【算法】滑动窗口——最小覆盖子串
|
1月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
1月前
|
算法
【算法】滑动窗口——将x减到0的最小操作数
【算法】滑动窗口——将x减到0的最小操作数
|
1月前
|
算法
【算法】滑动窗口——无重复字符的最长子串
【算法】滑动窗口——无重复字符的最长子串
|
1月前
|
算法
【算法】滑动窗口——长度最小的子数组
【算法】滑动窗口——长度最小的子数组
|
1月前
|
算法 容器
【算法】滑动窗口——串联所有单词的子串
【算法】滑动窗口——串联所有单词的子串
|
1月前
|
算法
【算法】滑动窗口——水果成篮
【算法】滑动窗口——水果成篮