Given an integer array
nums of length
n and an integer
target, find three integers in
nums such that the sum is closest to
Return the sum of the three integers.
- 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
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²).
We sort the array at the beginning, the sorting takes O(N) space.