Designing a fast algorithm which adds three numbers in array

Question

Given an array A, and a value called value. Does there exist three elements in A where their sum equals value?

Note that repeating elements are allowed. For example: I have an array 1 2 4 5 and value, 3.

A[0] + A[0] + A[0] = 3

---

I already created the naive brute-force O(n^3) algorithmic approach, but there appears to be a way through reduction to get this to Θ(n^2*log n) time (where log is in base two). My question is: How? I don't really see much way to improve this algorithm. (but then again I am new to this field).

Thanks in advance. I'd really appreciate any pointers or advice.

---

Thanks everyone for the help. I've designed version 2 of the algorithm!

answer = False
sort(A)
for i=1 to n
    for j=1 to n
        found = BinarySearch(t-A[i]+A[j])
        if found!=-1
            if (A[found]+A[i]+A[j])=value
                answer = True
return answer

Answer 1

This can indeed be done in $O(n^2 \log n)$ time. Here's a rough sketch.

Firstly, sort the array using any of the comparison based sort algorithm (like Merge Sort, Quick Sort etc.), this will take $O(n \log n)$ time.

Then, by using 2 nested loops going over the array (which will take $O(n^2)$ time) for each combination. Now, calculate sum of elements for each combination. Call this value $s$. Now, search value $\text{required number} - s$ in the array in $O(\log n)$ time. If each binary search for all $n^2$ possibilities returns false, then no such 3 elements exist. Otherwise, you can stop when you get first 3-tuple or enlist all such tuples.
Thus, the algorithm will take $O(n \log n) + O(n^2 \log n) = O(n^2 \log n)$ time.

Answer 2

Try all $N(N+1)/2$ pairs $(A[i], A[j])$ and look for $Value-A[i]-A[j]$ by dichotomic search in the array (sorted).