3Sum Closest


Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.


For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


You may assume that each input would have exactly one solution.


O(n^2) time, O(1) extra space.


Use 3 pointers:

  • First sort the array (O(n log n)). Set min to the max of integer value.
  • Then for each position i, use a left pointer at i + 1 and a right pointer at n - 1.
    • Calculate the sum of the 3 positions, if it's absolute value is less than the current min value, update min and remember the sum.
    • if the sum is smaller than the target, move left to the right, otherwise move right to the left.
  • return the recorded sum.

The loops take O(n^2) time, and the extra space is constant.

Online Judge