16. 3Sum Closest

解题思路：

与15题如出一辙，采用双指针法枚举，复杂度O(N^2)。

首先，对数组进行排序。然后，从第一个数字 i 开始遍历，每一层遍历中有两个指针 p, q 分别指向该数字后续的数组中的头尾两端，通过判断这三个数组的和与0的关系，移动头尾指针：

如果和大于0，返回target；如果和小于0，头指针后移；如果和等于0，分别移动头尾指针。

这里注意要考虑到数组中处理出现重复数字的情况。

如果 i 与 i - 1重复则直接跳过该项的遍历，如果 p 重复则 p++，如果 q 重复则 q++。

实现代码：

// 16. 3Sum Closest
int threeSumClosest(vector<int>& nums, int target) {
  sort(nums.begin(), nums.end());
  int p, q, sum;
  int gap = INT_MAX;
  int res;
  for (int i = 0; i < nums.size() - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    p = i + 1;
    q = nums.size() - 1;
    while (p < q) {
      sum = nums[i] + nums[p] + nums[q];
      if (sum == target) {
        return target;
      } else if (sum > target) {
        if (sum - target < gap) {
          gap = sum - target;
          res = sum;
        }
        while (nums[q] == nums[q - 1] && p < q)
          q--;
        q--;
      } else {
        if (target - sum < gap) {
          gap = target - sum;
          res = sum;
        }
        while (nums[p] == nums[p + 1] && p < q)
          p++;
        p++;
      }
    }
  }
  return res;
}

问题描述：

Given an arraynumsof_n_integers and an integertarget, find three integers innums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).