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.
思路： 排序，然后two pointer，复杂度 O(n^2)
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 16时24分28秒
4File Name :16.cpp
5************************************************ */
6class Solution {
7
8public:
9
10 int n;
11 int threeSumClosest(vector<int>& nums, int target) {
12 n = nums.size();
13 sort(nums.begin(),nums.end());
14 int mn = 0x3f3f3f3f;
15 int x,y,z;
16 for ( int i = 0 ; i <=n-3 ; i++)
17 {
18 int head = i+1;
19 int tail = n-1;
20 int tar = target - nums[i];
21 while (head<tail)
22 {
23 int cur = target-nums[i]-nums[head]-nums[tail];
24 if (abs(cur)<mn)
25 {
26 mn = abs(cur);
27 x = nums[i];
28 y = nums[head];
29 z = nums[tail];
30 }
31 if (nums[head]+nums[tail]==tar) return target;
32 if (nums[head]+nums[tail]<tar) head++;
33 else tail--;
34 }
35 }
36 return x + y + z;
37
38
39
40
41 }
42
43};