FB热乎跪经

n^2得到数组所有两两相加的和，放到一个hashmap中，key是和，value是一个数组，数组里的元素是一个string 比如“indexA+indexB”

最后轮询这个map，如果某个key对应的数组size大于1的话，就输出里面元素的两两组合

这种复杂度是o(n^2)?

qyf910813 发表于 2017-10-16 13:57
看了基本所有回帖，有说能优化到O(n^3)，但仔细想了下，这个是基于2Sum能用HashMap在O(n)时间里实现的，但 ...

意思是 2SUM 能优化到ON的前提是 给定一个target的情况下吗？

C（n,4）这个说法表示很同意。。

wjq987564321 发表于 2017-10-7 10:46
这个不错，感觉对了，另外值得注意的是A 可以等于CD 中的一个，etc 只是不能 A 和 B  等于C 和 D
所以不 ...

那这样的话，就不是4sum了， 4sum 里面 A, B, C , D各不相同

楼主最后怎么样了？这个题确实挺难的。

多谢楼主分享

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这题目最坏情况下输出都有n^4，例如考虑n个相同数字。。如果不考虑输出是O(n^2）