algorithm - 判断数组中是否有两个数之和为0

Question

假设有一个数组[1, 2, 9, 4, -5, -4]，我们需要找出是否有2个数字和为0。时间复杂度应该是O(n)，并且只是常数应使用额外的空间。允许修改原始数组。

我得到了这个作为面试问题，但没有弄清楚如何解决它。谢谢。

Answer 1

如果我们知道数组的数字范围，我们可以创建一个 HashMap ，该 HashMap 将消耗一个常量的额外空间来解决 O(n) 时间复杂度的问题。

#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{
        cout << "Not found" << endl;
    }

    return 0;
}