# LeetCode 16. 3Sum Closest

## Description

Given an array `nums` of n integers and an integer `target`, find three integers in `nums` such that the sum is closest to `target`. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

```Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
```

Constraints:

• `3 <= nums.length <= 10^3`
• `-10^3 <= nums[i] <= 10^3`
• `-10^4 <= target <= 10^4`

## Explanation

3Sum Closest is a follow-up question for two sum.

For 3Sum Closest, we are going to find the closet sum to the target. The closet sum could be the target itself or a number close to the target.

1. First, we can sort the array into ascending order.
2. Second, we declare an integer variable called closetSum. That’s the final value we are going to return.
3. Then we can iterate all the numbers in the array. Whenever visiting a number, we should find two numbers in the rest of array which adds the number closet to target. Once iteration finished, we get the result.

## Java Solution

``````class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return -1;
}

Arrays.sort(nums);

int closetSum = nums + nums + nums;

for (int i = 0; i < nums.length; i++) {
int left = i + 1;
int right = nums.length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(closetSum - target)) {
closetSum = sum;
}

if (sum < target) {
left++;
} else {
right--;
}
}
}

return closetSum;
}
}``````

## Python Solution

``````class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
three_sum_closest = sys.maxsize

nums = sorted(nums)

for i, num in enumerate(nums):
l = i + 1
r = len(nums) - 1

while l < r:
local_sum = nums[i] + nums[l] + nums[r]
if abs(local_sum - target)  < abs(three_sum_closest - target):
three_sum_closest = local_sum

if local_sum <= target:
l += 1
else:
r -= 1

return three_sum_closest

``````
• Time Complexity: O(Nlog(N))
• Space Complexity: O(1)