# 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

1. Use 3 pointers to point to the current element, next(left) element, and the last(right) element.
2. Sum the 3 elements.
3. 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.
4. 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)
5. 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.

--

--

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.