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

本文主要是介绍算法题：平均数为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]] = ielse:ans = max(ans, i - ans_dt[s[i]])print(ans)

这篇关于算法题：平均数为k的最长连续子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---