题解 | 平均数为k的最长连续子数组

#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ll = long int;
//本题中采用前缀和的方式。要求区间平均数为k，那么对每个元素减k，则区间平均数为0，区间和为0
int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> pre(n+1, 0);//pre存储区间和
    map<ll, int> mp;//map存储pre数组中每个值首次出现的下标
    mp[0] = 0;
    for(int i = 0; i < n; i++){
        ll a;
        cin >> a;
        a -= k;
        pre[i+1] = pre[i] + a;
        if(mp.count(pre[i+1]))  
            continue;//若map中已存在此值，则直接跳过，进入下一循环
        mp[pre[i+1]] = i+1;//此区间和的值第一次出现
    }
    int max_length = -1;//默认为-1，当出现大于0的值时才进行更新
    //sum为区间和，start为区间开头，length存储区间长度
    for(int i = 1; i <= n; i++){
        int length = i - mp[pre[i]];
        if(length > max_length && length)//length比max大且不为0
            max_length = length;
    }
    cout << max_length << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")