We are going to solve a problem that$$s a slight variant of the $3-$Sum problem, in which we don$$t want

to find the pair that sums to the target T anymore, instead we want to find the pair such that their

sum is the closest to the target T$,$ but notice that it may NOT necessarily smaller than T$,$ and our

goal is to find this sum value $($which could be T itself$)$ and return it$.$

More formally, the problem now is: given an array A of integers and Target T $,$ return the maximum

sum such that there exists i $=$ j $=$ k with A$[$i$]+$ A$[$j$]+$ A$[$k$]=$ sum and the absolute value of the

difference between sum and T the smallest among all possible value of sum. Again here, the elements

in the array is not necessarily all positive numbers, and sum maybe smaller or bigger than T or even

T itself $($in this case, the difference between T and sum is $0).$

To solve this problem, we can adjust the original $3$Sum problem by adding an additional variable to

track the minimum difference between a sum and T that we have seen so far, and at the end we just

return T minus that difference.

Complete the pseudocode below for this algorithm and give its running time: $[20$ points$]$

ThreeSumCloest$($A$[1..$n$],$ T $)$:

dif f $\backslash$infty

sort array A$[1..$n$]$

for k $1$ to n do

i$,$ j $$ k $+1,$ n

while i $<$ j do

sum $$

if sum $<$ T then

i $$

else if sum $>$ T then

j $$

else

return T

end if

$4$

if abs$($T $$ sum$)<$ abs$($dif f $)$ then

dif f $$ T $$ sum

end if

end while

return T $$ dif f

The running time of this algorithm is $.($in Big$-$O format is fine.$)$