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

前缀和+哈希表

思路：

1. 将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。
2. 进一步，为省去重复计算，使用前缀和处理数组。
3. 使用哈希表记录前缀和数组中每个值第一次出现的位置，遍历数组找到相同的值便计算距离并更新最大值即可。
4. 上述前缀和数组可优化为一个变量。

python参考代码：

import sys
from itertools import *
a = []
for line in sys.stdin:
    a += line.split()
a = list(map(int, a))
n, k = a[0], a[1]
a = a[2:]
for i in range(n): a[i] -= k
a = list(accumulate(a, initial = 0))
s = {}
ans = -1
for i, v in enumerate(a):
    if v not in s: s[v] = i
    else: ans = max(ans, i - s[v])
print(ans)

Java参考代码：

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        long[] nums = new long[n + 1];
        int i = 0, ans = -1;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 0);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            nums[++i] += in.nextInt() - k + nums[i - 1];
            if(!map.containsKey(nums[i])) map.put(nums[i], i);
            else ans = Math.max(ans, i - map.get(nums[i]));
        }
        System.out.println(ans);
    }
}

Java前缀和优化：

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        long s = 0;
        int ans = -1;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 0);
        // 注意 hasNext 和 hasNextLine 的区别
        for (int i = 1; i <= n; i++) { // 注意 while 处理多个 case
            s += in.nextInt() - k;
            if(!map.containsKey(s)) map.put(s, i);
            else ans = Math.max(ans, i - map.get(s));
        }
        System.out.println(ans);
    }
}