3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

方法1： 排序+二分法查找 算法复杂度O(n²log(n))

class Solution { private: int find_first_large(int left, int right, int val,vector<int>& nums){ while(left < right){ int middle = left + (right - left)/2; if(nums[middle] < val) left = middle + 1; else if(nums[middle] > val) right = middle; else return middle; } return left; } public: int threeSumClosest(vector<int>& nums, int target) { int MAX_difference = INT_MAX; int res; sort(nums.begin(),nums.end()); if(nums.size() < 3) return 0; for(int i = 0 ; i < nums.size() - 2; ++i){ if(i!=0 && nums[i]==nums[i-1]) continue; for(int j = i + 1; j < nums.size() - 1; ++j){ if(j!=i+1 && nums[j] == nums[j-1]) continue; int val = target - nums[i] - nums[j]; int val_index = find_first_large(j+1,nums.size()-1,val,nums); int temp_target = nums[i] + nums[j] + nums[val_index]; int difference = abs(temp_target - target); if(val_index != 0 && val_index !=j+1 ){ if( abs(nums[i] + nums[j] + nums[val_index-1] - target) < difference){ difference = abs(nums[i] + nums[j] + nums[val_index-1] - target); temp_target = nums[i] + nums[j] + nums[val_index-1]; } } if(difference < MAX_difference){ MAX_difference = difference; res = temp_target; } } } return res; } };

方法2：利用三个指针，算法复杂度 (O²)。

class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(),nums.end()); int max_dif = INT_MAX; int res ; for(int first = 0 ; first < nums.size()-2 ; ++first){ int second = first + 1, third = nums.size() - 1; while(second < third){ int temp_target = nums[first] + nums[second] + nums[third]; if(abs(temp_target-target) < max_dif){ max_dif = abs(temp_target-target); res = temp_target; } if( temp_target> target ) --third; else if(temp_target < target) ++second; else return target; } } return res; } };