Problems

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