LeetCode DD-2020006. 简单游戏（前缀和）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给出一个长度为 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 计算前缀和 presum
• 左右端点 [i, j] 间隔 m 距离，记录左端最大的前缀和 presum[i]，记为 a
• ans = 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阿明），一起加油、一起学习进步！