[LeetCode] 3Sum Closest

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).

分析：

同3sum 一样，但不用去重，

 1 class Solution {
 2 public:
 3     int threeSumClosest(vector<int> &num, int target) {
 4         
 5         int n =  num.size();
 6         
 7         sort(num.begin(), num.end());
 8         
 9         
10         int a, b,c;
11         int min_gap = INT_MAX;
12         int ret = 0;
13                 
14         for(int a = 0; a < n-2; a++)
15         {
16             b = a +1;
17             c = n-1;
18             
19             while(b < c)
20             {
21                 int sum = num[a] + num[b] + num[c];
22                 int gap = abs(sum - target) ;
23                 if(gap < min_gap)
24                 {
25                     min_gap = gap;
26                     ret = sum;
27                 }
28                 
29                if(sum < target)
30                     b++;
31                 else if(sum > target)
32                     c--;
33                 else
34                     return target;
35             }
36         }
37         
38         return ret;
39         
40     }
41 };