首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
haostart
中国科学技术大学 计算机类
发布于安徽
关注
已关注
取消关注
@Locam:
题解 | #平均数为k的最长连续子数组#
前缀和+哈希表思路:将输入数组中的元素减去k可将题目转化为“和为0的最长连续子数组”。进一步,为省去重复计算,使用前缀和处理数组。使用哈希表记录前缀和数组中每个值第一次出现的位置,遍历数组找到相同的值便计算距离并更新最大值即可。上述前缀和数组可优化为一个变量。python参考代码:import sysfrom 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] -= ka = list(accumulate(a, initial = 0))s = {}ans = -1for 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); }}
点赞 2
评论 1
全部评论
推荐
最新
楼层
滴滴
校招火热招聘中
官网直投
相关推荐
牛客952278
05-18 09:58
上海交通大学 计算机类
all in华子,拒绝焦虑
华子实习大开,等开奖了,拒绝焦虑,友友们都投华子了没?
点赞
评论
收藏
转发
23届在线找前端
04-26 10:48
前端工程师
感觉一眼假啊
点赞
评论
收藏
转发
牛客508681180号
04-21 17:50
研发工程师
都不如告诉我没通过!
点赞
评论
收藏
转发
二狗王
05-19 16:28
C++
大厂C++一定要学redis吗
现在在准备秋招,但是还没学过redis那些中间件,现在应该学一下redis还是好好搞一搞项目和八股
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
因为找实习和女朋友分手了
8347
2
...
写在最后,一个大专人9年的自述
7947
3
...
【有奖活动】浅聊一下我的实习⭐
7307
4
...
换导师
6668
5
...
双非本 腾讯WXG暑期已offer | 附面经
6009
6
...
开摆了,写小说去了
5801
7
...
爱华信华等华
5666
8
...
荣耀一面
5636
9
...
没offer的我们也很优秀偶
5146
10
...
华为暑期开奖
5062
正在热议
#
牛客帮帮团来啦!有问必答
#
842120次浏览
13253人参与
#
机械制造薪资爆料
#
322068次浏览
3747人参与
#
晒一晒我的offer
#
3489236次浏览
55477人参与
#
金三银四,你有感觉到吗
#
331772次浏览
4241人参与
#
0offer是寒冬太冷还是我太菜
#
430870次浏览
4959人参与
#
实习生如何通过转正
#
28057次浏览
366人参与
#
互联网公司评价
#
85631次浏览
1146人参与
#
我在牛爱网找对象
#
51303次浏览
337人参与
#
运营面经
#
15350次浏览
316人参与
#
如何缓解入职前的焦虑
#
36242次浏览
357人参与
#
海康威视求职进展汇总
#
102804次浏览
1224人参与
#
国企vs私企,你更想去?
#
20894次浏览
214人参与
#
毕业租房也有小确幸
#
27390次浏览
1497人参与
#
荣耀求职进展汇总
#
73120次浏览
745人参与
#
投了多少份简历才上岸
#
60920次浏览
981人参与
#
实习必须要去大厂吗?
#
14459次浏览
235人参与
#
你遇到过哪些神仙同事
#
19223次浏览
282人参与
#
职业发展规划如何回答
#
12198次浏览
85人参与
#
你已经投递多少份简历了
#
311849次浏览
4614人参与
#
实习工作,你找得还顺利吗?
#
43611次浏览
482人参与
牛客网
牛客企业服务