3Sum Closest

Problem

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.

Example

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).

Note

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

Challenge

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

Solution

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.