# Problem Statement

Given an integer array `nums`

of length `n`

and an integer `target`

, find three integers in `nums`

such that the sum is closest to `target`

.

Return *the sum of the three integers*.

# Key Ideas

- Use 3 pointers to point to the current element, next(left) element, and the last(right) element.
- Sum the 3 elements.
- If the difference between the current sum and target is smaller than the difference between our result and the target, set our result to the current sum.
- If current sum is larger than target, move the last(right) index to the left to get a smaller sum. (Remember
`target — sum = difference`

, so if larger sum = larger difference) - Otherwise, move the next(left) index to the right to get a larger sum.

# Time and Space Complexity

## Time Complexity

We sort the array initially, so it’s *O(N * log(N))*. We have a loop nested inside a loop so it is *O(N²)*. Overall the function takes *O(N * log(N) + N²)* which is asymptotically equivalent to *O(N²)*.

## Space Complexity

We sort the array at the beginning, the sorting takes *O(N)* space.