一道３sum 的类似题

北美农民 发表于 2012-10-31 18:30
好题一枚。 没做到n^2.

是O（2*n^2*log n）：

不错的方法，学习了

北美农民 发表于 2012-10-31 05:30
好题一枚。 没做到n^2.

是O（2*n^2*log n）：

a a a 后半截很精辟

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

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

为什么论坛半角英文a[i][i]无法输出？？[/i]
[i]本来要打a【i】（中括号是圆角）， 变成半角就不行了。。 再试一次a

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

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

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

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

这个题有意思。

如果不用额外空间，
首先2 sum是n^2的复杂度，3sum是n^3. 但是这个题没有给出和是多少。那么每个元素都可能是和。那么复杂度是n^4.

如果稍微用点技巧，先来个sort，就是n lgn复杂度。然后2sum复杂度是n。3sum就是n^2. 然后每个元素都可能是和，最后是n^3。

如果可以用空间，那就是hash了。复杂度也是n^3。感觉也只能做到这样。

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

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

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

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

北美农民 发表于 2012-11-5 08:45
版主，俺不是数学背景。。。

这个思路用“双向搜索”的思路形容比较恰当点吧。。。。

我觉得应该叫 预处理 吧