Google 电面 (05/11/2016)

一个小时前的面经，就问了一个问题，回头想想很简单，不过答得不咋好。 :-( 面试官小哥特别好，很轻松，前面瞎扯扯，让我先问问题，说后面写算法的时候会耽误点时间，所以先问问题，（满善解人意的）。 废话不多说，上题 您好！ 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 使用VIP即刻解锁阅读权限或查看其他获取积分的方式 游客，您好！ 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 VIP即刻解锁阅读权限 或 查看其他获取积分的方式 Unlock interview details and practice with AI Curated Interview Questions from Top Companies 也不知道那时候脑子怎么抽了，一直在回想刷过的题目，搞复杂了，好可惜。 希望将来面试的人好好审题。 Good Luck Everyone!

只想到一个用hashmap的O(n^2)做法。请问楼主当时怎么做？

楼主加油

简单做法就是遍历array里每个元素
然后按2sum做

请问楼主有没有更好的思路

yueliu2366 发表于 2016-5-12 03:51
只想到一个用hashmap的O(n^2)做法。请问楼主当时怎么做？

同只想到N^2 的hashamp

感觉只能和3sum差不多的做法? 排序2sum?

csehao 发表于 2016-5-13 03:34
感觉只能和3sum差不多的做法? 排序2sum?

貌似不能排序，要返回index的，排序就乱了

楼主可以解释一下怎么做的么？

感觉hash map 的O(n^2) 应该是最好的了吧

也觉得是hashmap O(n^2)，如果array有duplicates而且要求最后的indexes是不同的话会复杂点