Определите, существует ли A + B = C в массиве из n целых чисел

Это проблема, которую мой друг получил в качестве домашнего задания (в классе алгоритмов и структур данных). Он спросил меня об этом. Однако я не могу ее решить, и в течение последних нескольких дней я думал об этом некоторое время.

Есть n случайных целых чисел в диапазоне [0, 2 ³¹ ] -1] (могут быть дубликаты. Определите, удовлетворяют ли 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 ² ) слишком медленный. Мое решение не использует случайность. Однако я не уверен, что это важная часть проблемы.