> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/two_sum/3sum_closest.md).

# 16. 3Sum Closest

https\://leetcode.com/problems/3sum-closest/

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`

## Thoughts

数组中找三元组，它的和与target最近的。暴力法O(N^3)=>往O(N^2)优化。排序后nums\[i]作为最大元素的候选，在i元素前找和最接近target-nums\[i]的二元对，2sum。2sum用首尾双指针。

## Code

```python
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff, res = math.inf, 0 
        for i, num in enumerate(nums):
            l, r = 0, i - 1
            while l < r:
                s = sum((nums[l], nums[r], num))
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
                else:
                    return s
                if abs(s - target) < diff:
                    diff = abs(s - target)
                    res = s
        return res
        
```

```java
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null && nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);
        int cloest = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1, r = nums.length - 1;
            int res = target - nums[i]; 
            while (l < r) {
                if (Math.abs(nums[i] + nums[l] + nums[r] - target) < cloest) {
                    cloest = Math.abs(nums[i] + nums[l] + nums[r] - target);
                    sum = nums[i] + nums[l] + nums[r];
                }
                if (nums[l] + nums[r] < res) {
                    l++;
                } else if (nums[l] + nums[r] > res) {
                    r--;
                } else {
                    return target;
                }
            }
        }

        return sum;
    }
}
```

## Analysis

Errors:

1. 不需要考虑目标(res)应是sum-target还是target-sum，因为算法都是尽量向target靠。

TC: $$O(n^2)$$