Question： 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). Anwser 1： O（n^2） [cpp] class Solution { public: int threeSumClosest(vector<int> &num, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function int len = num.size(); assert(len >= 3); vector<int> num2; num2.assign(num.begin(), num.end()); sort(num2.begin(), num2.end()); int sum = num2[0] + num2[1] + num2[2]; int diff = abs(sum - target); int ret = sum; for(int i = 0; i < len - 2; i++){ int l = i + 1; int r = len - 1; while(l < r){ sum = num2[i] + num2[l] + num2[r]; if(sum == target) { return sum; } else if (sum < target){ l++; } else { r--; } if(abs(sum - target) < diff){ // more close, refresh diff and ret diff = abs(sum - target); ret = sum; } } } return ret; } }; 參考推薦： 3Sum 4Sum 數組中最大和的子數組
