题目:
Given an array of n integers and an integer , find three integers in such that the sum is closest to . Return the sum of the three integers. You may assume that each input would have exactly one solution. Example: | 给定一个包括 n 个整数的数组 和 一个目标值 。找出 中的三个整数,使得它们的和与 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 |
思路:和上一题类似,要保证和target的差 最小,那么定义 一个变量diff保存他们之间的差。首先排序,然后固定一个位置,剩下的两个数left从左往右,right从又往左,每确定两个数,我们求出此三数之和,然后算和给定值的差的绝对值存在newDiff中,然后和diff比较并更新diff和结果closest即可
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int closest = nums[0] + nums[1] + nums[2];
int diff = abs(closest - target);
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
int left = i + 1, right = nums.size() - 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;
}
};
参考:http://www.cnblogs.com/grandyang/p/4510984.html