题目来源：牛客
dd爱框框
题目描述：
读入 n ， x ，给出 n 个数 a[1] ， a[2] ，…， a[n] ，求最小的区间 [l,r] ，使 a[l] + a[l + 1] + … + a[r] ≥ x ，若存在相同长度区间，输出 l 最小的哪个。
输入描述：
第一行两个数，n (1≤n≤10000000) , x (1≤x≤10000)
第二行n个数 a[i] (1≤a[i]≤1000)
输出描述：
输出符合条件 l,r (保证有解)
示例1
输入：10 20
1 1 6 10 9 3 3 5 3 7
输出：3 5
解析
首先看题目，数据量是 107 级别，所以 O(n2) 和 O(nlogn) 的就不考虑了，暴力肯定做不了，只能使用 O (n) 算法，这种题很明显的 滑动窗口 解法，只能遍历一遍数组，不能回头，要注意怎么出入窗口。
代码实现
#include<iostream> using namespace std; const int N = 1e7 + 10; int arr[N]; int n, x; int main() { cin >> n >> x; for (int i = 1; i <= n; ++i) { cin >> arr[i]; } // 当前符合条件的最小区间，窗口左边，窗口右边 int len = N, left = 0, right = 0; // 区间和，最满足答案的左区间，最满足答案的右区间 int sum = 0, ansl = 0, ansr = 0; // 当窗口遍历完数组时结束 while (right <= n) { // 区间和加上新的右值 sum += arr[right]; // 满足条件，不断缩小窗口左边 while (sum >= x) { // 当前的最小区间 if (right - left + 1 < len) { // 更新答案 ansl = left; ansr = right; len = right - left + 1; } // 缩小区间左值 sum -= arr[left++]; } // 不满足 sum >= x，准备让窗口新增数据 ++right; } cout << ansl << ' ' << ansr; return 0; }
