美团笔试

美团笔试第四题

自认为写了个 O(n2)的解法,但是还是 过不去所有,超时

是因为dict的复杂度问题吗
import sys
n = sys.stdin.readline().strip()
n = int(n)
nums = list(map(int,sys.stdin.readline().strip().split()))

cnt = 0

dic = {}
a = set(nums)
# for i in range(len(nums)):
for num in a:
    if num not in dic:
        tmp = [0]*len(nums)

        # if nums[0]==nums[i]:
        #     dic[nums[i]][0]=1
        for j in range(len(nums)):
            if nums[j] == num:
                tmp[j] = tmp[j-1]+1
            else:
                tmp[j] = tmp[j-1]
        dic[num] = tmp
# print(dic)
for i in range(len(nums)-2):
    for j in range(i+1,len(nums)-1):
        if 3*nums[j]-nums[i] in dic:
            tmp = dic[3*nums[j]-nums[i]]
            cnt+=tmp[-1]-tmp[j]


        # for k in range(j+1,len(nums)):
        #     if nums[i]+nums[k]==3*nums[j]:
        #         cnt+=1
print(cnt)



#美团笔试##美团##美团笔试题#
全部评论
T4 AC代码
4 回复 分享
发布于 2022-08-13 18:58
用数组当hash map就可以过
4 回复 分享
发布于 2022-08-13 18:13
import java.util.*; class Main3 {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int[] arr = new int[n];         for (int i = 0; i < n; i++) {             arr[i] = sc.nextInt();         }         HashMap<Integer, Integer> hm = new HashMap<>();         for (int i = 1; i < n; i++) {             int t = hm.getOrDefault(arr[i], 0);             t++;             hm.put(arr[i], t);         }         long ans = 0;         for (int j = 1; j + 1 < n; j++) {             hm.put(arr[j], hm.getOrDefault(arr[j], 1) - 1);             for (int i = 0; i < j; i++) {                 int t = 3 * arr[j] - arr[i];                 ans += hm.getOrDefault(t, 0);             }         }         System.out.println(ans);     } }
3 回复 分享
发布于 2022-08-13 19:48
Hhhh 直接用一个大数组替代map就过了
1 回复 分享
发布于 2022-08-13 18:18
JAVA O(n^2)过了91
1 回复 分享
发布于 2022-08-13 18:13
Java暴力过了82
点赞 回复 分享
发布于 2022-08-20 15:29 重庆
ak了
点赞 回复 分享
发布于 2022-08-14 20:30
第三题是约瑟夫环吧?
点赞 回复 分享
发布于 2022-08-13 20:10
91,可是你们是怎么知道int爆了的,怎么调试出来的
点赞 回复 分享
发布于 2022-08-13 19:44
扑克牌复原 这道题可以来一个代码吗?
点赞 回复 分享
发布于 2022-08-13 19:13
哈希加两层for
点赞 回复 分享
发布于 2022-08-13 18:37
第一题怎么贪啊 一直以为是dp😓
点赞 回复 分享
发布于 2022-08-13 18:26
Python O(n^2)只过了36%
点赞 回复 分享
发布于 2022-08-13 18:20
那个找用二分
点赞 回复 分享
发布于 2022-08-13 18:18
蹲一下大牛讨论
点赞 回复 分享
发布于 2022-08-13 18:16
1
点赞 回复 分享
发布于 2022-08-13 18:14
前端笔试让写作文😂
点赞 回复 分享
发布于 2022-08-13 18:14
另一个帖子看到有人说int转long
点赞 回复 分享
发布于 2022-08-13 18:14
感觉和三数之和有点像,不知道为啥就过了18%
点赞 回复 分享
发布于 2022-08-13 18:13
这个用dfs求所有的三元组,然后判断是否符合即可
点赞 回复 分享
发布于 2022-08-13 18:11

相关推荐

07-23 11:23
门头沟学院 Java
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
昨天 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
5
3
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务