# 16. 3Sum Closest

Given an integer array `nums` of length `n` 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).
``````

Example 2:

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

Constraints:

• `3 <= nums.length <= 500`
• `-1000 <= nums[i] <= 1000`
• `-104 <= target <= 104`

``````class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int closest = nums[0] + nums[1] + nums[2], n = nums.size();
int diff = abs(closest - target);
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int newDiff = abs(sum - target);
if (diff > newDiff) {
diff = newDiff;
closest = sum;
}
if (sum < target) ++left;
else --right;
}
}
return closest;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/16

3Sum Smaller

3Sum

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

https://leetcode.com/problems/3sum-closest/discuss/7883/C%2B%2B-solution-O(n2)-using-sort

https://leetcode.com/problems/3sum-closest/discuss/7872/Java-solution-with-O(n2)-for-reference

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation