- 滑动窗口维护:使用两个指针
left 和 right 表示当前窗口的左右边界,维护窗口内元素的和 sum。 - 扩展窗口:
right 指针不断向右移动,将新元素加入窗口(sum += a[right])。 - 收缩窗口:当窗口内元素和
sum >= x 时:记录当前窗口长度 right - left + 1 和左端点 left。尝试通过移动 left 指针来缩小窗口(sum -= a[left], left++),直到窗口和小于 x。 - 记录最优解:在所有满足条件的窗口中,选择长度最小的;如果长度相同,选择左端点最小的。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];// 从下标 1 开始存数据:a[1], a[2], ..., a[n]
}
int sum = 0;// 当前窗口 [left, right] 内的元素和
int left = 1;// 滑动窗口的左边界,初始为 1
int best_len = n + 1;// 记录满足条件的最小区间长度(初始化为不可能的大值)
int best_left = 1;
int best_right = n; // 最优区间的左右端点(初始设为整个数组)
// 右指针 right 从 1 遍历到 n
for (int right = 1; right <= n; right++)
{
sum += a[right];
//只要当前窗口和 ≥ x,就尝试缩小左边界
while (sum >= x)
{
int c_len = right - left + 1;// 当前窗口长度
// 如果这个窗口比之前记录的更短 → 更新答案
if (c_len < best_len)
{
best_len = c_len;
best_left = left;
best_right = right;
}
sum -= a[left];// 尝试缩小窗口:去掉最左边的元素
left++; // 左边界右移
}
}
cout << best_left << " " << best_right << endl;
}