Determine if A+B=C exists in an array of n integers

Question

This is a problem a friend of mine received as his homework (in algorithm and data structure class). He asked me about this. However, I can't solve it and have been thinking about it for some time during the last several days.

There are n random integers in the range [0, 2³¹-1] (there may be duplicates. Determine if 3 numbers of these numbers satisfy A + B = C.

I first came up with a naive algorithm that's O(n²log n). I then came up with an algorithm that's O(n²). Here is the pseudo code:

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;

However, the problem states that 1 < n <= 10⁶. I believe O(n²) is too slow. My solution doesn't make use of the randomness. However, I'm not sure if this is an important part of the problem.