给出一个长度为 n 的数组 a,你需要在这个数组中找到一个长度至少为 m 的区间,使得这个区间内的数字的和尽可能小。
输入描述:
第一行包含一个正整数 n,m,表示数组的大小和所选区间的最小长度。(1<=n<100000)
第二行包含 n 个整数,中间用空格隔开 0 < = ∣ a i ∣ < = 1000 0<=|ai| <=1000 0<=∣ai∣<=1000。
输出描述: 输出仅包含一个正整数,表示所选区间的和。
输入样例:
5 3
1 2 3 4 5
输出样例:
6
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/1zD30O 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
[i, j]
间隔 m 距离,记录左端最大的前缀和 presum[i]
,记为 aans = min(ans, presum[j]-a)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m, val;
cin >> n >> m;
vector<int> presum(n+1);
for(int i = 1; i <= n; i++)
{
cin >> presum[i];
presum[i] += presum[i-1];//前缀和
}
int minsum = INT_MAX, a = INT_MIN;
for(int i = 0, j = m; j <= n; i++,j++)
{
a = max(a, presum[i]);//左端点的最大值
minsum = min(minsum, presum[j]-a);//间距满足要求
}
cout << minsum;
return 0;
}
28 ms 3.3 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!