2023-08-26 11:59 西安交通大学 算法工程师
关注
美团笔试最后一题题解
本轮笔试除了最后一题略微需要一点思维，其余都很容易。
友情提示：碰到涉及连续数组平均值、和的题，八九不离十要用前缀和。
1. 第一遍遍历数组，得到前缀和数组，假定为pre，数组长度为m+1
2. 题目等价于找出满足(pre[j]-pre[i])/(j-i) ＝ k的最长abs(j-i)。
整理得pre[j] - j*k＝pre[i] - i*k
所以创建一个新的数组dp ＝ [pre[i] - i*k for i in range(m+1)]
3. 题目问题转换到找出数组dp中值相等的最大索引距离，哈希表做即可
总时间复杂度为O(n)
友情提示：碰到涉及连续数组平均值、和的题，八九不离十要用前缀和。
1. 第一遍遍历数组，得到前缀和数组，假定为pre，数组长度为m+1
2. 题目等价于找出满足(pre[j]-pre[i])/(j-i) ＝ k的最长abs(j-i)。
整理得pre[j] - j*k＝pre[i] - i*k
所以创建一个新的数组dp ＝ [pre[i] - i*k for i in range(m+1)]
3. 题目问题转换到找出数组dp中值相等的最大索引距离，哈希表做即可
总时间复杂度为O(n)
全部评论
nagisawarm 楼主
楼主 西安交通大学 算法工程师
有时候针对数组没有思路的时候，不妨尝试先写出题目的表达式，尝试移项统一。这种类型的题很少见到，我还记得一年前第一次参加lc周赛（第84场双周赛t2）时候就碰到过这种。
递归到极致
江西农业大学 后端
只能说牛😊
百面而无一过😅
淘天集团_算法工程师
西交爷我给你跪了，这转化思路是真的牛爆了
牛客981931804号
门头沟学院 算法工程师
厉害了佬
这打野的走位就拟马呗离谱
Massachusetts Inst. of Technology 算法工程师
tql hxd
牛客86008488号
重庆大学 Java
卧槽，这个转换
nickbestwu
门头沟学院 算法工程师
牛的这个思路 我双指针单次遍历只通过45%
鱼虾yi整碗
门头沟学院 C++
思路清晰，学到了
找工作要多久
门头沟学院 Java
厉害了
来个_offer
东南大学 C++
学到了，思路太顶了
躺平的菜鸟
门头沟学院 后端
tql 前缀和超时之后就不知道怎么优化了
伊欧菲斯kkk
小马智行_算法工程师
转化一下，每个值都减去k，就变成了和为0的最长子序列问题。然后前缀和，找其中距离最远且相等的两项
相关推荐
查看7道真题和解析 
Asp1rin：自己平心而论每天刷牛客的时间和学习的时间哪个更多 点赞 评论 收藏
分享
大拿老师：这个简历，连手机号码和照片都没打码，那为什么关键要素求职职位就不写呢？
从上往下看，都没看出自己到底是产品经理的简历，还是电子硬件的简历？
这是一个大问题，当然，更大的问题是实习经历的描述是不对的
不要只是去写实习流程，陈平，怎么去开会？怎么去讨论？
面试问的是你的产品功能点，是怎么设计的？也就是要写项目的亮点，有什么功能？这个功能有什么难处？怎么去解决的？
实习流程大家都一样，没什么优势，也没有提问点，没有提问，你就不得分
另外，你要明确你投的是什么职位，如果投的是产品职位，你的项目经历写的全都是跟产品无关的，那你的简历就没用
你的面试官必然是一个资深的产品经理，他不会去问那些计算机类的编程项目
所以这种四不像的简历，在校招是大忌 点赞 评论 收藏
分享
