leetcode 16. 3Sum Closest (k-sum问题，two pointer)
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 {
public:
1 int n;
2 int threeSumClosest(vector<int>& nums, int target) {
3 n = nums.size();
4 sort(nums.begin(),nums.end());
5 int mn = 0x3f3f3f3f;
6 int x,y,z;
7 for ( int i = 0 ; i <=n-3 ; i++)
8 {
9 int head = i+1;
10 int tail = n-1;
11 int tar = target - nums[i];
12 while (head<tail)
13 {
14 int cur = target-nums[i]-nums[head]-nums[tail];
15 if (abs(cur)<mn)
16 {
17 mn = abs(cur);
18 x = nums[i];
19 y = nums[head];
20 z = nums[tail];
21 }
22 if (nums[head]+nums[tail]==tar) return target;
23 if (nums[head]+nums[tail]<tar) head++;
24 else tail--;
25 }
26 }
27 return x + y + z;
}
};