Problem:
Question- Give an algorithm to check if 3 numbers in an array add to a given sum in theta(n^2*log(n)) time:
i, j, and k do not have to be distinct.
For example, if A[1..7] = [28, -70, -23, 92, 56, -33, -77] and t = -47, the answer would be “yes”, because if we set i = 2, j = 5, and k = 6, we have A[i] + A[j] + A[k] = -70 + 56 - 33 = -47.
(Hint: compute the following two sets of numbers: one set contains all possible values of A[i] + A[j], and the other set contains all possible values of t ? A[k]).
I already did this in n^3 time by using 2 nested loops, now i need it in n^2*log(n) time
Please explain the algorithm in detail to check the problem.