编程面试问题/如何查找数组中的任何两个整数是否为零？

Question

不是作业问题,而是一个可能的面试问题......

1. 给定一个整数数组,写一个算法,检查任何两个的总和是否为零.
2. 这个解决方案的大O是什么？

寻找非暴力方法

Answer 1

使用查找表:扫描数组,将所有正值插入表中.如果遇到相同幅度的负值(可以在表格中轻松查找); 它们的总和将为零.查找表可以是用于节省内存的哈希表.

该解决方案应为O(N).

伪代码:

var table = new HashSet<int>();
var array = // your int array
foreach(int n in array)
{
     if ( !table.Contains(n) ) 
         table.Add(n);
     if ( table.Contains(n*-1) )
         // You found it.;
}

Answer 2

其他人提到的散列表解决方案通常是O(n),但它也可以O(n^2)在理论上退化.

这是一个Theta(n log n)永不退化的解决方案:

Sort the array (optimal quicksort, heap sort, merge sort are all Theta(n log n))
for i = 1, array.len - 1
    binary search for -array[i] in i+1, array.len

如果您的二进制搜索返回true,那么您可以停止算法并获得解决方案.