塔子哥的平均数-美团2023笔试(codefun2000)

题目链接
塔子哥的平均数-美团2023笔试(codefun2000)

题目内容

给定一个正整数数组a1 ,a2 ,…,an，求平均数正好等于k的最长连续子数组的长度

输入描述

输出描述

输出一个整数，表示最长满足题目条件的长度。

样例1

输入

5 2
1 3 2 4 1

输出

3

样例1解释

题解1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int n, k, a[N], ans;
LL pre[N];

unordered_map<LL, int> ump;
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		pre[i] = pre[i - 1] + a[i];
	}
	LL x;
	ump[0]=0;
	for(int i = 1; i <= n; i++){
		x = pre[i] - 1LL*k*i;
		if(ump.count(x) == 0) ump[x] = i;
		else {
			ans = max(ans, i - ump[x]);
		} 
	}
	printf("%d\n", ans);
	
	return 0;
}