16.LEETCODE3Sum Closest《越努力，越幸运》

3Sum Closest 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 1:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4 方法一：暴力解法

int threeSumClosest(vector<int> &nums, int target) { int l = nums.size(); int first,second, third; int small = INT_MAX; int r; if (l == 3) return nums[0] + nums[1] + nums[2]; for (first = 0; first < l; first++) { for (second = first + 1; second < l-1; second++) { third=l-1; if (nums[first] + nums[second] + nums[third] - target == 0) return nums[first] + nums[second] + nums[third]; else { while (third > second) { int temp = abs(nums[first] + nums[second] + nums[third] - target); if (temp < small) { small = temp; r=nums[first] + nums[second] + nums[third]; } third--; } } } } return r; }

方法二：参考题解后 使用双指针

int threeSumClosest(vector<int> &nums, int target) { //利用排序+双指针，固定一个数将剩下的数两头寻找 int res = nums[0] + nums[1] + nums[2]; //保存结果 int a, b, c; int l = nums.size(); sort(nums.begin(), nums.end()); int small=INT_MAX; for (a = 0; a < l-2; a++) { c = l - 1; b = a + 1; while (a < b && b < c) { if (small > abs(nums[a] + nums[b] + nums[c] - target)) { small = abs(nums[a] + nums[b] + nums[c] - target); res = nums[a] + nums[b] + nums[c]; } if (nums[a] + nums[b] + nums[c] - target > 0) c--; else { if (nums[a] + nums[b] + nums[c] - target < 0) b++; else return nums[a] + nums[b] + nums[c]; } } } return res; }