Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
52 lines (43 sloc) 1.62 KB
/*
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).
*/
/*
Hints:
I think 016 is simple than B.
There is an algorithm with time complexity less than O(n^2).
1. sort(nums.begin(), nums.end())
2. A idea similar to 015:
Fix the first number.
Use two pointer to find another two number.
The head pointer points to the one behind the first number.
The tail pointer points to the tail of the vector.
3. Compare the absolute value of the difference between the sum of three numbers and the target.
And if(sum < target) ++l else if(sum > target) --r else if(sum == target) return
4. Please don't skip duplicate values. This will lead to mistakes.
*/
class Solution {
protected:
int tmp, diff = 0x7fffffff, answer;
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
for(int i=0;i<nums.size()-2;i++){
int l = i + 1;
int r = nums.size() - 1;
while(l < r){
tmp = nums[i] + nums[l] + nums[r];
if(abs(tmp - target) < diff){
diff = abs(tmp - target);
answer = tmp;
}
if(tmp < target) ++l;
else if(tmp > target) --r;
else if(tmp == target) return answer;
}
}
return answer;
}
};