arrays - 判断n个整数数组中是否存在A+B=C

Question

这是我的一个 friend 收到的作业(算法和数据结构类)。他问我这件事。但是，我无法解决它，最近几天一直在思考这个问题。

在[0, 2³¹-1]范围内有n个随机整数(可能有重复，判断这3个数是否满足 A + B = C。

我首先想出了一个 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 位这一事实。