16. 3Sum Closest

First of all, sort the array. If you don't sort the array, the running time will be n!, i.e. approximately O(n^3). After sort, you can have one pointer scan from 0 to n-2 and inside the scanning loop, create two pointers j and k starting from i+1 and n-1 respectively. And then there will be three cases:
Case 1: nums[i] +  nums[j] + nums[k] == target. Then return immediately
Case 2: nums[i] + nums[j] + nums[k] < target. Since array is sorted, we just need to move j to right.
Case 3: nums[i] + nums[j] + nums[k] > target. Same idea as Case 2, we just need to move k to left.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int closest = nums[0] + nums[1] + nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i > 0 && nums[i] == nums[i-1]) continue;  
9:        int j = i+1;  
10:        int k = nums.size()-1;  
11:        while (j < k) {  
12:          int sum = nums[i] + nums[j] + nums[k];  
13:          if (sum == target) return sum;  
14:          if (abs(target-sum) < abs(target-closest)) {  
15:            closest = sum;  
16:          }  
17:          if (sum < target) j++;  
18:          else k--;  
19:        }  
20:      }  
21:      return closest;  
22:    }  
23:  };  

When I revisited this problem, I had a bit more concise solution.

1:  class Solution {  
2:  public:  
3:    int threeSumClosest(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int minSum = nums[0]+nums[1]+nums[2];  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        int l = i+1, r = nums.size()-1, t = target-nums[i];  
9:        while (l < r) {  
10:          if (abs(t-nums[l]-nums[r]) < abs(minSum-target)) minSum = nums[l]+nums[r]+nums[i];   
11:          if (nums[l]+nums[r] == t) return target;  
12:          else if (nums[l]+nums[r] > t) r--;  
13:          else l++;  
14:        }  
15:      }  
16:      return minSum;  
17:    }  
18:  };