首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用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); }}
点赞 7
评论 1
全部评论
推荐
最新
楼层
暂无评论,快来抢首评~
相关推荐
07-28 18:59
苏州大学 集成电路IC设计
对日本祛魅
说实话,去日本旅游有很大的吸引力,日本是个很有魔力的地方,不仅仅是因为其干净,还有其商品的质量高。这个国家总是安安静静的,就连司机也总是对每一个乘客点头行礼,周围环境建筑也是一种动漫风格。刚开始几天被日本的干净和安静惊讶到了,佩服他们的秩序。渐渐地,慢慢地就发现不对劲了。以我短时间的观察,他们感觉一直被压抑着,例如夜晚不敢回家在街头驻足的中年男性。被各种规矩束缚着,一旦有人破坏了他们的规矩,无论有意无意,他们什么反应都有可能给出。这个社会的包容度很低。清一色的西装革履。连雨伞都潜移默化地规定透明的和黑色的长伞。基本看不到折叠伞。他们是真的活得累。因为有其他国家生活经验,试着入乡随俗,就会发现战...
我对___祛魅了
点赞
评论
收藏
分享
07-31 15:53
已编辑
五邑大学 Java
双非二本找不到实习准备秋招,简历求指教
如题,双非二本找了一个半月实习没几个要简历的想直接准备秋招了,但是感觉简历好简单但又不知道怎么改有点想改成两页但是第二页我担心太空了不好看求指教,听劝
无实习如何秋招上岸
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
06-21 11:29
鱼皮翻车了?牛油们怎么看
凉风落木楚山秋:
他们两都收获了流量,只有爷浪费了时间
点赞
评论
收藏
分享
07-25 11:09
门头沟学院 Java
26届Java后端开发,求建议!
开学大四,准备尝试下秋招。没有过实习经历,还有一会吗?兄弟们
无实习如何秋招上岸
点赞
评论
收藏
分享
07-31 12:25
东华大学 模拟IC设计
兆易创新
终于有面试了提前批模拟ic真的太卷了
兆易创新一面42人在聊
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
百度提前批,三面被推迟一周,喜提秋招第一凉
1.1W
2
...
虾皮秋招一面
3573
3
...
他拿大厂SSP Offer打牌是什么概念啊?25届双非之光
3467
4
...
觉得研发高人一等的这辈子有了
2768
5
...
百度提前批 三面
2032
6
...
最强本科✌
1759
7
...
也是逆天了
1451
8
...
被猿辅导挂了简历,但我想说...
1405
9
...
虾皮一面凉经
1368
10
...
上班一周,工资还没拿,先欠公司两千
1338
创作者周榜
更多
正在热议
更多
#
工作中哪个瞬间让你想离职
#
66149次浏览
583人参与
#
找工作如何保持松弛感?
#
92299次浏览
1121人参与
#
中兴秋招
#
207471次浏览
2304人参与
#
如何快速融入团队?
#
19106次浏览
221人参与
#
Offer比较,你最看重什么?
#
194341次浏览
1324人参与
#
和同事相处最忌讳的是__
#
27205次浏览
258人参与
#
秋招被确诊为……
#
166813次浏览
797人参与
#
参加过提前批的机械人,你们还参加秋招么
#
86729次浏览
1417人参与
#
投格力的你,拿到offer了吗?
#
87779次浏览
586人参与
#
虾皮求职进展汇总
#
251011次浏览
1888人参与
#
你最希望上岸的公司是?
#
136153次浏览
709人参与
#
计算机专业还有必要去大厂卷吗
#
38781次浏览
184人参与
#
柠檬微趣工作体验
#
6940次浏览
40人参与
#
26届的你,投了哪些公司?
#
51614次浏览
526人参与
#
地平线求职进展汇总
#
52768次浏览
371人参与
#
通信硬件岗投递时间线
#
18983次浏览
69人参与
#
简历上的经历如何包装
#
32648次浏览
872人参与
#
我对___祛魅了
#
53777次浏览
468人参与
#
你跟室友的关系怎么样?
#
8424次浏览
124人参与
#
你遇到最难的面试题目是_
#
17758次浏览
210人参与
#
一人推荐一个值得去的通信/硬件公司
#
191757次浏览
1888人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务