algorithm - Finding three elements in an array whose sum is closest to a given number -

given array of integers, a₁, a₂, ..., a_n, including negatives , positives, , integer s. need find 3 different integers in array, sum closest given integer s. if there exists more 1 solution, of them ok.

you can assume integers within int32_t range, , no arithmetic overflow occur calculating sum. s nothing special randomly picked number.

is there efficient algorithm other brute force search find 3 integers?

is there efficient algorithm other brute force search find 3 integers?

yep; can solve in o(n²) time! first, consider problem p can phrased equivalently in different way eliminates need "target value":

original problem p: given array a of n integers , target value s, there exist 3-tuple a sums s?

modified problem p': given array a of n integers, there exist 3-tuple a sums zero?

notice can go version of problem p' p subtracting s/3 each element in a, don't need target value anymore.

clearly, if test possible 3-tuples, we'd solve problem in o(n³) -- that's brute-force baseline. possible better? if pick tuples in smarter way?

first, invest time sort array, costs initial penalty of o(n log n). execute algorithm:

for (i in 1..n-2) {   j = i+1  // start right after i.   k = n    // start @ end of array.    while (k >= j) {     // got match! done.     if (a[i] + a[j] + a[k] == 0) return (a[i], a[j], a[k])      // didn't match. let's try little closer:     //   if sum big, decrement k.     //   if sum small, increment j.     (a[i] + a[j] + a[k] > 0) ? k-- : j++   }   // when while-loop finishes, j , k have passed each other , there's   // no more useful combinations can try i. } 

this algorithm works placing 3 pointers, i, j, , k @ various points in array. i starts off @ beginning , works way end. k points last element. j points i has started at. iteratively try sum elements @ respective indices, , each time 1 of following happens:

• the sum right! we've found answer.
• the sum small. move j closer end select next biggest number.
• the sum big. move k closer beginning select next smallest number.

for each i, pointers of j , k gradually closer each other. pass each other, , @ point don't need try else i, since we'd summing same elements, in different order. after point, try next i , repeat.

eventually, we'll either exhaust useful possibilities, or we'll find solution. can see o(n²) since execute outer loop o(n) times , execute inner loop o(n) times. it's possible sub-quadratically if fancy, representing each integer bit vector , performing fast fourier transform, that's beyond scope of answer.

---

note: because interview question, i've cheated little bit here: algorithm allows selection of same element multiple times. is, (-1, -1, 2) valid solution, (0, 0, 0). finds exact answers, not closest answer, title mentions. exercise reader, i'll let figure out how make work distinct elements (but it's simple change) , exact answers (which simple change).