snapchat一道错题

ThinkDeeper2

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

seattle电面，已跪。遇到了一道题，在提示下提出了一种错误的解法。上来分享一下。题目是给出一个数组，输出符合a^2+b^2=c^2 的(a,b,c)组合。
brute force很简单，三个for循环, O(n^3). 要求优化，提出了用3s

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

z+t 进行判断。
所以这个解法是错的。不知道大家有什么想法。但很显然，面试官没有发现这个错，否则在写之前就应该否定。

cooldogrj

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

cynthiazp

其实这是个数学题，跟算法没多大关系。优化的方法应该是找出 3 4 5， 5 12 13这类基础勾股数，然后他们的倍数也是勾股数。
楼主看这里： http://bbs.csdn.net/topics/320021598

bitzyq

这个数组都是正数吗。。。如果abc都是正数的话，c肯定是最大的，数组排序后是不是可以倒着找c？ab肯定在c之前的那段数组里面，然后假设a是开头，b是结尾，然后用逼近的方法看有没有解？这样应该是O(n^2)。

不都是正数的话应该要先建一个平方值构成的数组再找吧。

ThinkDeeper2

bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话，c肯定是最大的，数组排序后是不是可以倒着找c？ab肯定在c之 ...

正解。那是我的想法错了。

dukecat0613

bitzyq 发表于 2017-7-8 02:20
这个数组都是正数吗。。。如果abc都是正数的话，c肯定是最大的，数组排序后是不是可以倒着找c？ab肯定在c之 ...

正解 on2 判断第三个数是不是完全平方数就ok 了

asdfyou6

这个题还使用3sum吧采用 hashmap 只是多一些考虑的条件而已比如选出来的 3个数是xyz xzy zxy 3种情况以及相应的去重

byrlhb

就是有负数也没有关系，把每个值的平方算一下重新排个序就好了

justin

asdfyou6 发表于 2017-7-7 14:16
这个题还使用3sum吧采用 hashmap 只是多一些考虑的条件而已比如选出来的 3个数是xyz xzy zxy 3种情况 ...

我觉得这个才是正解。去重的情况通过排序就可以解决了。排序之后再扫描的时候，跳过相邻相同的数。