# 找出数组中是否有两个数之和为0

##### 问题描述投票：1回答：2

algorithm dynamic
##### 2个回答
0

``````#include <iostream>
#include <cmath>

using namespace std;

int main(){

int arr[]={1, 2, 9, 4, -5, -4};
int n = sizeof(arr)/sizeof(arr[0]);

const int N=1000001; // the maximum non negative value for arr[i] is 1,000,000
int hashmap [N];

bool found=false;

for (int i=0; i<N; i++){ //initialize the hashmap
hashmap[i]=0;
}

for (int i=0; i<n; i++){
int temp = abs( arr[i] );
if (  hashmap[ temp ] == 0  ){ // no collision
if (arr[i] >= 0){
hashmap[ temp ] = 1;   //mark the hashmap 1 for positive arr[i]
}else{
hashmap[ temp ] = -1;  //mark the hashmap -1 for negative arr[i]
}
}else{                         //collision
if (hashmap[ temp ] == 1 && arr[i] <= 0){
found = true;
break;
}else if (hashmap[ temp ] == -1 && arr[i] > 0){
found = true;
break;
}
}
}

if (found){
cout << "Found" << endl;
}else{
}

return 0;
}
``````

0

`a :=`数组中最大的数字。`b :=`数组中最小的负数。

`bits := 2 * max(a,-b)`

`m`是具有`bits`位的整数变量。 （均以0初始化）

``````// Now we read the array (time **O(n)**).
for(i=0; n>i; i++){
if(0<=a[n]){
if(m.testBit(2*a[n] + 1))
return true;  // negative value was already there
m.setBit(2*a[n]);
}
else{
if(m.testBit(2*a[-n]))
return true;  // positive value was already there
m.setBit(2*(-n) + 1);
}
return false;
``````