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.
