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

问题描述 投票:1回答:2

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

我把这个作为面试问题,但没有弄清楚如何解决。谢谢。

algorithm dynamic
2个回答
0
投票

如果知道数组的数字范围,我们可以创建一个散列图,该图将消耗一个恒定的额外空间来解决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;
}

0
投票

一般评论:如果我们可以修改原始数组,并且对数组中的值的大小没有限制,则可以在数组的每个元素中存储尽可能多的信息。参见https://en.wikipedia.org/wiki/Gödel_numbering


在这种特殊情况下,您可以更简单地完成它。

我们只需要知道像这样完成的数组中是否存在一个值及其负值:

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;

如果使用第一个数组元素存储m(第一次设置m后就不再需要原始值了,它就不会占用额外的空间。

但是这有点作弊,因为我们需要数组元素具有足够的位。

但是我们只用了O(n)时间,根本没有多余的空间。


推荐问答