【笔试】算法的暴力美学——牛客 NC221681：dd爱框框
一、题目描述
二、算法原理
思路：滑动窗口
1）定义两个指针，一开始都为0，cur 从左开始遍历，定义一个 sum 来表示 prev 到 cur 的之间的值的总和，当 sum >= x 时，我们要根据题目条件来保存 prev 和 cur 的值；
2）当 sum >= x 时，我们记录完 prev 和 cur 的值的之后，sum -= arr[ prev ]，prev++ ，往后走，只要满足条件 sum >= x 我们就要记录 prev 和 cur 的值，不断重复上面的工作；
3）当 sum < x 时，cur++，sum += arr[ cur ]；
4）直至遍历完整个数组；
三、代码实现
#include <iostream> #include <vector> using namespace std; int main() { //准备工作 int n,x; cin >> n >> x; vector<int> arr(n,0); for(int i = 0; i < n; i++) cin >> arr[i]; int index[2] = {0};//保存最后的结果 //滑动窗口 int cur = 0; int prev = 0; int sum = 0; while(cur < n) { sum += arr[cur]; while(sum >= x)//入窗口 { if(index[0] == 0 && index[1] == 0) { index[0] = prev; index[1] = cur; sum -= arr[prev++]; continue; } int length = index[1] - index[0]; int camplen = cur - prev; if(length == camplen || length > camplen) { if(prev < index[0] || length > camplen) { index[0] = prev; index[1] = cur; } } sum -= arr[prev++]; } //出窗口 cur++; } cout << index[0] + 1 << ' ' << index[1] + 1 << endl; return 0; }
