我要招人

去企业版

首页 > 试题广场 >

给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、

[单选题]

给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、c、d，使得 a+b+c+d =sum，最快的平均时间复杂度是____。

```
O(N^2)
```
```
O(log N)
```
```
O(N)
```
```
O(N^3)
```
```
O(N^2LogN)
```
```
O(N^4)
```

查看正确选项

notlie

O(N^3LogN)的算法：

三重for循环穷举a,b,c的值，剩下d = sum-a-b-c,使用二分查找(数组事先排好序)来确定d是否存在。

O(N^2LogN)的算法：

预先枚举c,d得到c+d的n^2个数字并排好序。

双重for循环穷举a,b的值，再使用二分查找确定c+d是否存在。

c+d的值得出来后同样枚举得出c,d的值。（或者在第一步就浪费一些空间将c+d对应的c,d存好，此时直接取出即可。)

排序及循环二分查找都为O(n^2logn)时间，总的O(n^2logn)时间。

发表于 2015-08-17 22:30:45 回复(7)

百瑞

求数列中两两的和，O（N^2）；

对刚才求完的这N^2个数排序，O(N^2*log(N^2))=O(N^2*logN);

对排好的序列找两者的和为sum,从两头向中间凑，O（N^2）；

合计：O(N^2*logN)

发表于 2015-09-20 10:05:44 回复(3)

lhbug1

求2sum时候，由于无序所以先要排序，时间度为o(nlogn)；对于4sum，如果要最快可以借鉴2sum，对两两数之和存储，然后采用2sum方法，这个排序时间o（2*n^2logn）,而查找的时间为o(n^2), 所以总的时间应该为（n^2logn）

发表于 2015-08-19 22:27:41 回复(2)

小杨vita

最快应该是N^2，先算任意两个数c+d的和，复杂度O（N^2），放入hashset，这时候用两个for循环遍历a，b，然后在hashset里头找sum-(a+b)，复杂度是O(N^2)，加起来就是O(N^2)

发表于 2015-09-28 18:19:49 回复(0)

ZQ_123

这题我认为是A

我们先从设计2sum的O(n)算法开始解释算法思想。

2sum也就是找a+b=sum,

2 sum 的O(n) 算法:

开hashtable,

for every element i in array，hashtable[i] 设置True.

检查hashtable[sum-i],是否为true。

hashtable的插入和搜索都是O(1),所以最后复杂度是O(n)

所以很自然的，

对4 sum问题，也就是a+b+c+d，我们有O(n^2) 算法:

枚举元素求得 n^2个数字。

for every pair of numbers c,d 对hashtable[(c+d)]添加 tuple(c,d)

然后对每个元素检查 hashtable[sum-(c+d)]是否有数字

发表于 2016-09-07 10:54:04 回复(0)

啊啊啊62

要得到答案只需要三步：

第一步：枚举x+y，存入一个数组，时间复杂度O(N^2)

第二步：排序，随便啥吧，反正第一步等着给你垫底儿了，O(N*logN)或者O(N^2)

第三步：一个指针从头到屁股，另一个从屁股到头，凑和。O(N)，这个不会去看剑指offer

所以，取最大为O(N^2)

发表于 2017-08-23 19:51:30 回复(0)

牛客520063396号

有没有可能，先做所有两数的和然后做a+b=sum

发表于 2022-10-08 17:16:19 回复(0)

有莘不殁

先把所有数两两相加配出，并记录原始下标，排序，再用2sum, 排除下标重合。。 O(N^2 )

编辑于 2017-10-23 20:45:16 回复(0)

foreverfruit

看了楼上各位大神的解答，我弱弱的问一下，从2sum最快时间复杂度O(n)可以类推到4sum的最快时间复杂度，在2sum中利用hash表时可以找到这两个元素的，但是4sum。。。如何找到4个元素呢，只能找到两个求和的值啊，难道还要再分别来两次hash表？

发表于 2016-09-07 15:43:46 回复(0)

Gason

我清楚地记得关于这道题有一篇很经典的文章中讨论过，利用哈希表4sum问题最快可以达到O(n^2)的。而2sum用哈希，可以达到O(n)的。

编辑于 2015-08-22 15:43:34 回复(0)

牛客243885号

能不能用类似背包问题的方法解决?求大神解答

发表于 2015-08-20 20:11:11 回复(0)

牛客537606号

其实如果不考虑空间复杂度的话，应该是有O(n^2)解的。对数组A，两两求和，可以得到数组B(时间复杂度为O(n^2))。于是就变成2-sum啦。T=O(n^2) + O(n) = O(n^2)

编辑于 2015-08-18 21:02:35 回复(0)

marsandmars

为啥我百度到的说是O(N∧3)呢……求大神解答

发表于 2015-08-06 22:24:10 回复(5)

最爱可乐

leetcode k sum 问题

发表于 2015-06-14 14:21:17 回复(0)

ABCD

对于时间复杂度实在是很难理解的。先找出a大概为二分之一的sum，再找出b大概是四分之一的sum，再找出c和d分别大概为八分之一的sum，如何计算时间复杂度？

发表于 2015-06-03 19:36:16 回复(1)

陌莫Fun

我觉得思路是利用快速排序思想，排序之后利用动态规划算法从而求解，选E

发表于 2015-05-06 22:51:10 回复(0)

提交观点

问题信息

设计算法工程师阿里巴巴集团 2015

来自：阿里巴巴2015算法工...

上传者：陈木木

难度：

16条回答 531收藏 21084浏览

给定一个整数sum，从有N个无序元素的数组中寻找元素a、b、

问题信息

热门推荐

相关试题