请教一道L的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道L的题

请教一道L的题# JobHunting - 待字闺中

h*e2014-12-11 08:12

1 楼

congs

N*82014-12-11 08:12

2 楼

Given a array of positive integers, find all possible triangle triplets that
can be formed from this array.
eg: 9 8 10 7
ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10
Note : array not sorted, there is no limit on the array length
geeks4geeks有类似的，但是只是求三角形个数的，能用n^2事件复杂度解出来。但是如
果求所有的三边的输出，感觉还是要n^3。请教大家的优化方法。

h*e2014-12-11 08:12

3 楼

我日，被骗了，今天才9号。

w*a2014-12-11 08:12

4 楼

感觉就是3 sum变种题

m*t2014-12-11 08:12

5 楼

白忙活了，是明天。

r*72014-12-11 08:12

6 楼

要是需要输出所有的话，必然要n^3吧，extreme的case是所有的组合都是valid的，就
必然有n^3个结果啊

that

【在 N*****8 的大作中提到】

: Given a array of positive integers, find all possible triangle triplets that
: can be formed from this array.
: eg: 9 8 10 7
: ans: 9 8 10, 9 8 7, 9 10 7, 7 8 10
: Note : array not sorted, there is no limit on the array length
: geeks4geeks有类似的，但是只是求三角形个数的，能用n^2事件复杂度解出来。但是如
: 果求所有的三边的输出，感觉还是要n^3。请教大家的优化方法。