> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/7.two-pointers/593sum-closest.md).

# 59.3Sum Closest

## 1.Description(Medium)

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.

### Notice

You may assume that each input would have exactly one solution.

**Example**

For example, given array*S*=`[-1 2 1 -4]`, and target =`1`. The sum that is closest to the target is`2`.*(-1 + 2 + 1 = 2)*.

[**Challenge**](https://www.lintcode.com/en/problem/3sum-closest/#challenge)

O(n^2) time, O(1) extra space

## 2.Code

3sum问题的变种。一样的遍历每个数，对剩余数组进行双指针扫描。区别仅仅在于当：

sum = A\[left] + A\[right]

(1) sum = target时直接返回

(2) sum != target时，在相应移动left/right指针之前，先计算abs(sum-target)的值，并更新结果。

```
 public int threeSumClosest(int[] numbers, int target) {
        if(numbers==null || numbers.length<3){
            return 0;
        }
        Arrays.sort(numbers);
        int mindiff=Integer.MAX_VALUE;
        for(int i=0;i<numbers.length-2;i++){
            int left=i+1;
            int right=numbers.length-1;
            while(left<right){
                //这里diff用sum-target,之后返回的时候直接返回target+diff即可。
                int sum=numbers[left]+numbers[right]+numbers[i];
                int diff=sum-target;
                //这样的话diff的正负就不对了
                //mindiff=Math.min(mindiff, Math.abs(diff));
                //正确的写法是：
                if(Math.abs(diff)<Math.abs(mindiff)){
                    mindiff=diff;
                }

                if(diff==0){
                    return target;
                }
                else if(diff<0){
                    left++;
                }else{
                    right--;
                }
            }           
        }
        return target+mindiff;
    }
```