What numbers in the unordered list can be represented as a sum of 3 other numbers in the list?

Question

I came across the following question from an online interview and came up with a solution O (N ^ 2).
I want to know if there is a better way to solve this problem?

Problem: What numbers in an unordered list can be represented as a sum of 3 other numbers in a list?

My O (N ^ 2) solution:

• Create a hash map that stores the sum of all two pairs of elements.
  for example hashmap.insert (a [i] + a [j]), 0 <= i, j <= N-1

• After the hashmap is constructed in step 1 (takes O (N ^ 2) time,
  I will select a pair of nC2 pairs and see if this pair contains the third element and the sum,
  i.e. for all pairs of two elements (a [p ], a [q]), where 0 <= p, q <= N-1 Find if hashmap contains (a [q] - a [p])

Answer 1

It could not be better than O(N^2), because if you would then solve one of the most difficult problems in computer science, which should solve the problem with three sums less than O (N ^ 2). The question remains open whether the 3-sum can be solved less than O (N ^ 2).

3-amount