【题解】NowCoder dd爱框框

本文主要是介绍【题解】NowCoder dd爱框框，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：牛客

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

解析

首先看题目，数据量是 10⁷ 级别，所以 O(n²) 和 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;
}

这篇关于【题解】NowCoder dd爱框框的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---