Example Example 1:
Input:[2,7,11,15],3 Output:20 Explanation: 2+7+11=20 Example 2:
Input:[-1,2,1,-4],1 Output:2 Explanation: -1+2+1=2 Challenge O(n^2) time, O(1) extra space
Notice You may assume that each input would have exactly one solution.
解法1：类似3sum，只是每次都要更新result。 代码如下：
class Solution { public: /** * @param numbers: Give an array numbers of n integer * @param target: An integer * @return: return the sum of the three integers, the sum closest target. */ int threeSumClosest(vector<int> &numbers, int target) { int N = numbers.size(); if (N < 3) return 0; sort(numbers.begin(), numbers.end()); int p1 = 0, p2 = 0, p3 = 0; int result = numbers[0] + numbers[1] + numbers[2]; for (int p3 = 3; p3 < N; ++p3) { int newTarget = target - numbers[p3]; p1 = 0, p2 = p3 - 1; while(p1 < p2) { int twoSum = numbers[p1] + numbers[p2]; int threeSum = twoSum + numbers[p3]; if (abs(result - target) > abs(threeSum - target)) { result = threeSum; } if (twoSum < newTarget) { p1++; } else if (twoSum > newTarget) { p2--; } else { break; } } } return result; } };