【笔试】算法的暴力美学——牛客 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;
}