fb面经里的这个题有优于O(n^2)的解法么？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

fb面经里的这个题有优于O(n^2)的解法么？

fb面经里的这个题有优于O(n^2)的解法么？# JobHunting - 待字闺中

r*72015-02-27 08:02

1 楼

You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
values that satisfy A+B = C + D, where A,B,C & D are integers values in the
array.
Eg: Given [3,4,7,1,2,9,8] array
The following
3+7 = 1+ 9 satisfies A+B=C+D
so print (0,2,3,5)

l*n2015-02-27 08:02

2 楼

No! if you just want to find out all the possible sums, it is O(n^2), it is
hard bottom.

the

【在 r****7 的大作中提到】

: You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of
: values that satisfy A+B = C + D, where A,B,C & D are integers values in the
: array.
: Eg: Given [3,4,7,1,2,9,8] array
: The following
: 3+7 = 1+ 9 satisfies A+B=C+D
: so print (0,2,3,5)

d*i2015-02-27 08:02

3 楼

如果数组允许重复怎么做

y*t2015-02-27 08:02

4 楼

o(n)就行了...
提示：从左往右+从右往左

l*n2015-02-27 08:02

5 楼

怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted

【在 y****t 的大作中提到】

: o(n)就行了...
: 提示：从左往右+从右往左

r*72015-02-27 08:02

6 楼

我觉得不一定啊，感觉sort过之后是不是可以有的case给skip掉呢？

is

【在 l******n 的大作中提到】

: No! if you just want to find out all the possible sums, it is O(n^2), it is
: hard bottom.
:
: the

r*72015-02-27 08:02

7 楼

没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
的target，貌似也还是要遍历很多种可能。

【在 l*****n 的大作中提到】

: 怎么个从左往右从右往左啊。。。怎么想都不对啊
: 这array也没说是sorted

n*s2015-02-27 08:02

8 楼

sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

【在 r****7 的大作中提到】

: 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
: 的target，貌似也还是要遍历很多种可能。

l*n2015-02-27 08:02

9 楼

如果数组有重复的，怎么办？

【在 n*******s 的大作中提到】

: sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

x*92015-02-27 08:02

10 楼

如果用指针来找的话，至少要确定三个指针才能推出第四个。所以我觉得即使数组是有
序的，用双（多）指针法也是不可行的。
等大神解答。

d*62015-02-27 08:02

11 楼

就算把范围cut了，还是要计算比如n/2或者n/4内所有数字的组合，结果还是O(n^2)

【在 n*******s 的大作中提到】

: sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

r*72015-02-27 08:02

12 楼

l*n2015-02-27 08:02

13 楼

No! if you just want to find out all the possible sums, it is O(n^2), it is
hard bottom.

the

【在 r****7 的大作中提到】

d*i2015-02-27 08:02

14 楼

如果数组允许重复怎么做

y*t2015-02-27 08:02

15 楼

o(n)就行了...
提示：从左往右+从右往左

l*n2015-02-27 08:02

16 楼

怎么个从左往右从右往左啊。。。怎么想都不对啊
这array也没说是sorted

【在 y****t 的大作中提到】

: o(n)就行了...
: 提示：从左往右+从右往左

r*72015-02-27 08:02

17 楼

我觉得不一定啊，感觉sort过之后是不是可以有的case给skip掉呢？

is

【在 l******n 的大作中提到】

: No! if you just want to find out all the possible sums, it is O(n^2), it is
: hard bottom.
:
: the

r*72015-02-27 08:02

18 楼

没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
的target，貌似也还是要遍历很多种可能。

【在 l*****n 的大作中提到】

: 怎么个从左往右从右往左啊。。。怎么想都不对啊
: 这array也没说是sorted

n*s2015-02-27 08:02

19 楼

sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

【在 r****7 的大作中提到】

: 没有sort倒是可以sort，cheaper than n^2，然后用类似2sum的算法么？可是没有固定
: 的target，貌似也还是要遍历很多种可能。

l*n2015-02-27 08:02

20 楼

如果数组有重复的，怎么办？

【在 n*******s 的大作中提到】

: sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

x*92015-02-27 08:02

21 楼

如果用指针来找的话，至少要确定三个指针才能推出第四个。所以我觉得即使数组是有
序的，用双（多）指针法也是不可行的。
等大神解答。

d*62015-02-27 08:02

22 楼

就算把范围cut了，还是要计算比如n/2或者n/4内所有数字的组合，结果还是O(n^2)

【在 n*******s 的大作中提到】

: sort完了变成1234789，然后找A+B=C+D并且满足和在5(1+4)和13(4+9)之间的？

a*02015-02-27 08:02

23 楼

vector> 2sumSum(vector& a)
{
vector> res;
size_t n=a.size();
if(n<4) return res;

unordered_map>> umap;
for(size_t i=0;ifor(size_t j=i+1;jint sum=a[i]+a[j];
if(umap.find(sum)!=umap.end()) {
for(auto e: umap[sum]){
res.push_back({i,j, e.first, e.second});
}
}

umap[sum].push_back(make_pair(i, j));
}
}
return res;
}