算法题：平均数为k的最长连续子数组

问题描述

1.题目描述

给定 n个正整数组成的数组，求平均数正好等于 k 的最长连续子数组的长度。

2.I/O描述

输入描述：
第一行输入两个正整数n和k，用空格隔开。
第二行输入n个正整数a_i，用来表示数组。

输出描述：
如果不存在任何一个连续子数组的平均数等于k，则输出-1。
否则输出平均数正好等于 k 的最长连续子数组的长度。

3.I/O示例

示例1
输入例子：
5 2
1 3 2 4 1
输出例子：
3
例子说明：
取前三个数即可，平均数为2。

---

算法分析：

1.把原数组nums中每一个元素都减去k得到一个新数组
2.构建前缀和数组（前面补0 防止答案在最前端）
3.找到数组中距离最远的元素（用哈希辅助）

---

具体代码

# 数据输入
a = input().split()
length = int(a[0])
avg = int(a[1])
info = input().split()
# 获得新数组
int_array = [int(char) - avg for char in info]

# 初始化前缀、数组和字典
s = [0]
ans_dt = {}


# 构建前缀和数组
for i in range(1, length+1):
    item = s[i - 1] + int_array[i - 1]
    s.append(item)

# 获取相同元素的最远距离
ans = -1
for i in range(len(s)):
    if s[i] not in ans_dt.keys():
        ans_dt[s[i]] = i
    else:
        ans = max(ans, i - ans_dt[s[i]])

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27