FB热乎跪经

ctcs

排序 O(n log n), 然后O(n ^ 2) 枚举两个数的和，设和为k，用O(n)找sum 为k的数字（只在去掉的两个数字之内的index找），一共O(n ^ 3)

wjq987564321

ctcs 发表于 2017-10-7 10:17
排序 O(n log n), 然后O(n ^ 2) 枚举两个数的和，设和为k，用O(n)找sum 为k的数字（只在去掉的两个数字之内 ...

朋友，没有懂啊，一共四个数，为什么要找sum为k的数字呢？有没有code写一蛤

wangshuang1211

wjq987564321 发表于 2017-10-7 09:59
额，我觉得你说的有道理，可是找到一组ABCD需要的时间是O(N2)吗，因为我保存的是List, 如果你新发现了一 ...

找出所有的pair brute force就行了，时间是n*(n-1)/2

石之冬静

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

石之冬静

石之冬静发表于 2017-10-7 10:26
对仔细一想觉得楼主说的挺对的，楼主有没有和面试官确认给出的int[] array 输入里面的每个element有没有 ...

额没看到楼主后面的回复，忽略我吧，让我再想想

wjq987564321

wangshuang1211 发表于 2017-10-7 10:26
找出所有的pair brute force就行了，时间是n*(n-1)/2

可是关键是pair的个数可能是O(N2)个啊。。。

ctcs

wjq987564321 发表于 2017-10-7 10:19
朋友，没有懂啊，一共四个数，为什么要找sum为k的数字呢？有没有code写一蛤

用2Sum的办法找和为k的2个数字的index, O(n)

点菜大司马

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

wangshuang1211

wjq987564321 发表于 2017-10-7 10:32
可是关键是pair的个数可能是O(N2)个啊。。。

n*(n-1)/2就是O(n)啊，n choose 2

补充内容 (2017-10-7 10:40):
说错，O(n^2)

夜皇雪

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