# [LeetCode] 16. 3Sum Closest 最近三数之和

2021年09月15日 阅读数：1

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.html

Example:java

```Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).```

15. 3Sum 三数之和 的拓展，这题是让找到和目标数最接近的数字组合，仍是用3Sum的方法，遍历每一个数，对剩余数组进行双指针扫描，只是此次要设一个变量minDiff来记录最小差值的绝对值，若是当前三数的和与目标数相等，直接返回三数和。若是三数和与目标数的差的绝对值小于minDiff，则此组合更接近目标数，result变为此组合的和，迭代查找直到结束， 返回result。python

Java:数组

```public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosestV2(int[] numbers,int target) {
if (numbers == null || numbers.length < 3) {
return Integer.MAX_VALUE;
}

Arrays.sort(numbers);

int length = numbers.length;
int closest = Integer.MAX_VALUE / 2;

for (int i = 0; i < length - 2; i++) {
int pl = i + 1;
int pr = length - 1;

while (pl < pr) {
int sum = numbers[i] + numbers[pl] + numbers[pr];
if (sum == target) {
return sum;
} else if (sum < target) {
pl++;
} else {
pr--;
}
closest = Math.abs(sum - target) < Math.abs(closest - target) ?
sum : closest;
}
}
return closest;
}
}
```

Python:post

```class Solution(object):
def threeSumClosest(self, nums, target):
nums, result, min_diff, i = sorted(nums), float("inf"), float("inf"), 0
while i < len(nums) - 2:
if i == 0 or nums[i] != nums[i - 1]:
j, k = i + 1, len(nums) - 1
while j < k:
diff = nums[i] + nums[j] + nums[k] - target
if abs(diff) < min_diff:
min_diff = abs(diff)
result = nums[i] + nums[j] + nums[k]
if diff < 0:
j += 1
elif diff > 0:
k -= 1
else:
return target
i += 1
return result
```

C++:url

```class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
if(num.size()<3) return INT_MAX;
sort(num.begin(),num.end());
int minDiff = INT_MAX;
for(int i=0; i<num.size()-2; i++) {
int left=i+1, right = num.size()-1;
while(left<right) {
int diff = num[i]+num[left]+num[right]-target;
if(abs(diff)<abs(minDiff)) minDiff = diff;
if(diff==0)
break;
else if(diff<0)
left++;
else
right--;
}
}
return target+minDiff;
}
};
```