# LeetCode16. 3Sum Closest（对撞指针）

## LeetCode16. 3Sum Closest（对撞指针）

• Medium
• Accepted：245,713
• Submissions：694,617

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:

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

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

### 链接

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

### 题解

LeetCode15. 3Sum（对撞指针）没有什么区别，此外，因为只要找到最接近target的和，所以无需去重，做法一样，排序后一层循环加对撞指针，时间复杂度$O(n^2)$。

### 代码

• Runtime: 12 ms, faster than 97.48% of C++ online submissions for 3Sum Closest.
• Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for 3Sum Closest.
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
int ans = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; ++i)
{
if (i > 0 && nums[i] == nums[i-1])
continue;
int l = i + 1, r = n - 1, sum;
while (l < r)
{
sum = nums[i] + nums[l] + nums[r];
if (sum == target) // 相等直接返回
return sum;
if (abs(sum - target) < abs(ans - target)) // 找到最接近的
ans = sum;
if (sum < target)
++l;
else if (sum > target)
--r;
}
}
return ans;
}
};

The end.
2019年2月17日 星期日