确定A + B = C是否存在于n个整数的数组中

Question

这是我的一个朋友作为他的家庭作业(在算法和数据结构类中)收到的问题.他问我这件事.但是,我无法解决它,并且在过去的几天里一直在思考它.

有Ñ范围随机整数[0,2 ³¹ -1](有可能重复.确定是否3个数字,这些数字的满足甲 + 乙 = Ç.

我首先提出了一个O(n ² log n)的天真算法.然后我想出了一个O(n ²)的算法.这是伪代码:

sort(a); // non-descending
for (i = 0; i < n; i++) {
  j = i; k = i + 1;
  while (j < n && k < n) {
    if (a[i] + a[j] == a[k])
      return true;
    else if (a[i] + a[k] < a[j])
      k++;
    else
      j++;
  }
}
return false;

然而,问题表明1 < n <= 10 ⁶.我相信O(n ²)太慢了.我的解决方案没有利用随机性.但是,我不确定这是否是问题的重要部分.

Answer 1

一般问题是3SUM-Hard,是否存在优于二次算法的问题是开放的.

因此,如果您需要更快的算法,您可能需要利用它们是32位的事实.