题目描述
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).
解题思路
- 遍历一个序列
- 类似于原来3sum，我们找 nums[i] + nums[begin] + nums[end]
- 找上面三个数 3sum - target 看是否小于一个值，如果小于，更新结果即可
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int size = nums.size();
int diff = INT_MAX;
sort(nums.begin(), nums.end());
int res = 0;
for(int i = 0; i < size; i++){
int begin = i + 1;
int end = size - 1;
int temp = 0 - target;
while(begin < end){
int sum = nums[i] + nums[begin] + nums[end];
if(sum == target){
return sum;
}
if(abs(sum - target) < diff){
diff = abs(sum - target);
res = sum;
}
if(sum < target){
begin++;
}else{
end--;
}
}
}
return res;
}
};
