## 原题

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).
```

## 代码

[code lang=”cpp”]
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
vector<int> rs;
int l = nums.size(), dist = 100000000;
sort(nums.begin(), nums.end());

for (int i = 0; i < l – 2; ++i) {
int f = i + 1, b = l – 1;
if (i – 1 >= 0 && nums[i] == nums[i – 1]) continue;
while (f < b) {
if (nums[f] + nums[b] + nums[i] – target > 0) {
if (abs(dist) > abs(nums[f] + nums[b] + nums[i] – target)) {
dist = nums[f] + nums[b] + nums[i] – target;
}
while(nums[b] == nums[–b]) {}
} else if (nums[f] + nums[b] + nums[i] – target < 0) { if (abs(dist) > abs(nums[f] + nums[b] + nums[i] – target)) {
dist = nums[f] + nums[b] + nums[i] – target;
}
while(nums[f] == nums[++f]) {}
} else {
return target;
}
}
}

return dist + target;
}
};
[/code]

Share:

This site uses Akismet to reduce spam. Learn how your comment data is processed.