判断一包含n个整数a[]中是否存在i、j、k满足a[i] +

[单选题]

判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度为（）

```
O(n)
```
```
O(n^2)
```
```
O(nlog(n))
```
```
O(n^2log(n))
```

查看答案及解析

ASLLDHDMAXFUN

for(int j=0; j<n; j++) {
    vis[a[j]]=1;
}
for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
        if(vis[a[j]+a[i]]==1)return true;
    }
}
return false;

编辑于 2018-09-17 12:04:03 回复(0)

classObject

sort(arr);//O(n)O(nlogn)O(n^2)
int i,j,k;
for(k=0;k<arr.length;k++)
    for(i=0,j=arr.length-1;i<=j;){
       if(arr[k]>arr[i]+arr[j]) i++;
        else if(arr[k]<arr[i]+arr[j]) j--;
        else break;
    }//O(n^2)

编辑于 2018-09-10 21:24:05 回复(0)

为什么不问问神奇海螺呢

其实这题这样问是有问题的，没说明a[i]的范围，没说明时限。

发表于 2018-11-20 18:37:42 回复(0)

雁掠南疆

两重循环计算a[i]+a[j],O(n^2)

发表于 2018-09-10 14:38:42 回复(0)

中年失业

所以是不能使用hash表吗

发表于 2018-10-27 13:38:28 回复(0)

Zhuoooo

for(let i = 0; i < length; ++i){
    for(let j = i + 1; j < length; ++j){
        if(arr.includes(arr[i] + arr[j])){
            return true
        }   
    }
}
return false

发表于 2018-09-10 16:10:17 回复(0)