思路:先对vector进行排序,然后夹逼计算,时间复杂度O(n^2),里面需要注意在判断完边界后,先计算thres和result,然后处理下标,这里不需要考虑重复情况。
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int sum = 0; int thres = INT_MAX; int result = nums[0] + nums[1] + nums[2]; for(int i=0; i<nums.size()-2; ++i) { int j = i+1; int k = nums.size() - 1; while(j<k) { if(nums[i] + nums[j] + nums[k] < target) { if(fabs(nums[i] + nums[j] + nums[k] - target) < thres) { thres = fabs(nums[i] + nums[j] + nums[k] - target); result = nums[i] + nums[j] + nums[k]; } ++j; } else if(nums[i] + nums[j] + nums[k] > target) { if(fabs(nums[i] + nums[j] + nums[k] - target) < thres) { thres = fabs(nums[i] + nums[j] + nums[k] - target); result = nums[i] + nums[j] + nums[k]; } --k; } else { return nums[i] + nums[j] + nums[k]; } } } return result; } };
原文:http://www.cnblogs.com/chengyuz/p/6536548.html