思路：前缀和

给定一个数组，要求找到一个连续子数组的平均值为$k$，并且其长度是符合条件子数组里最长的，求其长度。

可以考虑前缀和的做法来解此题。要求连续子数组平均值为$k$，让每个数$a_i^{、}=a_i-k$，那么如果一段连续子数组平均值和为$k$，则这一段数组的和为$0$。$\sum{a_i^{、}=\sum{a_i}-k*length}=0$。

扩展开来，如果前缀和中出现某两个位置的值相等，那么根据前缀和的定义，他们间的这一段的和为$0$，那么这一段的长度就是备选答案之一。

所以我们需要使用哈希来存储前缀和中每个数第一次出现的位置，当其又一次出现时，就可以计算长度作为备选答案。

代码

C++

AC

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
#define ll long long

const int maxn=1e5+10;
int n;
ll k,a[maxn];
map<ll,int> id;

int main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>k;
	int ans = -1;
	id[0]=-1;// 初始化定义，0的第一次出现出现在-1位置，计算时如果为0，相当于一直取到数组最左边 
	ll tmp=0;
	for(int i=0;i<n;++i){
		cin>>a[i];
		a[i]-=k;
		tmp+=a[i];// 累加值 
		if(id.find(tmp)!=id.end()){// 如果累加值出现过，说明存在一段连续和为k的子数组 
			ans=max(ans,i-id[tmp]);
		}else{// 不存在，则记录其位置 
			id[tmp]=i;
		}
	}
	cout<<ans;
	
	return 0;
}

python

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = -1
id = {0: -1}  # 初始化定义，0的第一次出现出现在-1位置，计算时如果为0，相当于一直取到数组最左边
tmp = 0

for i in range(n):
    a[i] -= k
    tmp += a[i]  # 累加值
    if tmp in id:  # 如果累加值出现过，说明存在一段连续和为k的子数组
        ans = max(ans, i - id[tmp])
    else:  # 不存在，则记录其位置
        id[tmp] = i

print(ans)

Java

import java.util.Scanner;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long k = scanner.nextLong();
        
        int ans = -1;
        HashMap<Long, Integer> id = new HashMap<>();
        id.put(0L, -1); // 初始化定义，0的第一次出现出现在-1位置，计算时如果为0，相当于一直取到数组最左边 
        long tmp = 0;
        
        for (int i = 0; i < n; ++i) {
            long ai = scanner.nextLong();
            ai -= k;
            tmp += ai; // 累加值
            if (id.containsKey(tmp)) { // 如果累加值出现过，说明存在一段连续和为k的子数组
                ans = Math.max(ans, i - id.get(tmp));
            } else { // 不存在，则记录其位置
                id.put(tmp, i);
            }
        }
        
        System.out.println(ans);
    }
}

题目内容

给定一个正整数数组$a_1,a_2,...,a_n$，求平均数正好等于k的最长连续子数组的长度

输入描述

第一行输入两个正整数$n$和$k$

第二行输入n个正整数$a_i$

，用来表示数组

$1 \leq n \leq 1e5$

$1≤ k,a_i \leq 1e9$

输出描述

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

样例

输入

5 2
1 3 2 4 1

输出

3