Best Sum of Three Elements in a Sequence I encountered the following problem:

Given an integer sequence $\left(s_1,s_2,\dots,s_n\right)$ and an integer $l$, find $$\min\left|s_i+s_j+s_k-l\right|,$$ where $i\neq j\neq k\neq i$, and return $s_i+s_j+s_k$.

For example: given $\left(-1,2,1,-4\right)$ and $l=1$, following the above criteria, we obtain $-1+2+1=2$.
I wrote a program that considers all $n\choose3$ possibilities; it runs in $O(n^3)$ time.
Is there a faster approach? If so, could you hint me toward it?
 A: Here's another $O(n^2\log n)$ algorithm, similar to Ross Millikan's but slightly different.  Start by sorting the $s_i$'s into increasing order, i.e., assume $s_1\le s_2\le\cdots\le s_n$.  This can be done in $O(n\log n)$ steps, so we can assume the $s_i$'s came this way.  Given such an ordered sequence, and given any number $S$, straightforward "bisection" will locate an integer $k$ such that $s_k\le S\le s_{k+1}$ (allowing for $s_0=-\infty$ and $s_{n+1}=\infty$) in $O(\log n)$ steps.  The algorithm now runs through the $O(n^2)$ pairs $(s_i,s_j)$, lets $S=l-s_i-s_j$, finds the corresponding integer $k$ for each value of $S$, and keeps track of whether a new minimum is obtained.  To be somewhat more precise, use the replacement formula
$$M\to\min\{M,(S-s_{k-2}),(S-s_{k-1}),(S-s_k),(s_{k+1}-S),(s_{k+2}-S),(s_{k+3}-S)\}$$
but knocking out any of the terms with a subscript equal to $i$ or $j$.  (This last wrinkle is to meet the stipulation $i\not=j\not=k\not=i$.)
Added later:  It occurs to me that one might as well assume that $l=0$ in describing an algorithm, by replacing each $s_i$ with $3s_i-l$.  This means, in effect, that the complexity problem boils down to looking for an algorithm that takes two sequences
$$0\le p_1\le p_2\le \cdots\le p_n\le\infty \quad {and}\quad 0\le q_1\le q_2\le\cdots\le q_n\le\infty$$
and seeks to minimize $|p_i+p_j-q_k|$ with $i\not=j$.  (I'm omitting various details of how the OP's problem connects to this one, but I hope the general nature of the connection is clear.  What's unclear, to me at least, is whether this throws any light on the original problem.  Still, I thought it worth mentioning.)
A: You can do $O(n^2 \log n)$.  Let us work on the same problem without $s_k$, so we are minimizing $|s_i+s_j-l|$ and show an $O(n \log n)$ algorithm.  Then you can just loop $k$ from $1$ to $n$ to get $O(n^2 \log n)$.  Sort the $s$'s into an array $t_1,t_2\dots t_n$ with $t_1 \lt t_2 \lt \dots t_n$  Now compute $t_1+t_n-l$  If it is positive, you may improve things by replacing $t_n$ by $t_{n-1}$.  If it is negative, you may improve things by replacing $t_1$ by $t_2$.  Keep stepping in until you meet in the middle and report the best result you found.
A: Since $k$ is given, the value of $s_k - k$ is also known, so you only need to look through all possible $ij$ pairs; that's $O(n^2)$.  
