滑动窗口（C++、C语言）
【模板】滑动窗口
难度：初阶
时间限制：1000ms
内存限制：256mb
题目描述
按顺序给出 n 个整数 a1...an，计算其中最长一段连续的总和不超过 k 的序列长度。
输入格式
第一行两个整数 n,k
第二行 n 个整数 a1...an
输出格式
一个整数表示答案
#include <iostream>
#include <deque>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
deque<int> q;
int res = 0, sum = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
q.push_back(x);
sum += x;
while (!q.empty() && sum > k)
{
sum -= q.front();
q.pop_front();
}
res = max(res, (int)q.size());
}
cout << res << endl;
return 0;
}
#include <stdio.h>
int main()
{
int n, k;
scanf("%d %d", &n, &k);
int a[n];
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
int maxLen = 0;
int sum = 0;
int start = 0;
for(int i = 0; i < n; i++)
{
sum += a[i];
while(sum > k)
{
sum -= a[start];
start++;
}
maxLen = maxLen > (i - start + 1) ? maxLen : (i - start + 1);
}
printf("%d", maxLen);
return 0;
}
该回答内容部分引用GPT，GPT_Pro更好的解决问题
滑动窗口是一种算法思想，它的目的是在数据集中找到所有满足特定条件的子序列，这种算法思想可以在C++和C语言中实现。
滑动窗口算法的步骤如下：
1、首先，在数据集中定义一个滑动窗口，该窗口的大小由你自己决定；
2、然后，将滑动窗口从左向右滑动，直到遇到满足条件的子序列；
3、最后，将滑动窗口右边界向右滑动，重复这个过程，直到遇到数组的末尾。
以输入的 n=2, k=8 为例，如果我们使用 C 语言来实现滑动窗口算法，我们首先需要定义一个整型数组a[2]，来存储输入的数据：
int a[2];
然后我们需要使用两个变量来表示滑动窗口的左边界left和右边界right：
int left=0, right=0;
接下来我们就开始进入滑动窗口的核心循环部分，我们需要先计算当前子序列的和sum：
int sum=0; // 计算当前子序列的和sum
for(int i=left;i<right;i++)
sum+=a[i];
然后判断当前子序列是否满足大小不超过k的条件：
if(sum<=k) // 当前子序列大小不超过k时执行语句
// 执行你想要的代码
else { // 当前子序列大小超过k时执行语句
sum-=a[left]; // 更新sum
left++; // 更新left
}
最后我们将right++来更新右边界并重复上面的步骤：
right++; // 更新right
直到遇到数组的末尾，即right==n时退出循环。
最后通过对比left和right之间相差多少步来得出最长一段连续总和不超过k的序列长度。
因此，通过上面步骤我们就可以用C++和C语言实现滑动窗口算法。
如果回答有帮助，望采纳。
- 这篇博客也许可以解决你的问题👉 ：c语言 -- 滑动窗口
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632