3Sum Closest (C++ code)

 LeetCode: 3Sum Closest II
难度3，出现频率1
Given an array S of n integers, find three integers in S such that the sum 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).

思路: 先排序，然后sliding window，记得每次更新最小和。 时间复杂度O(n^2), 空间O(1)。

int threeSumClosest(vector<int> &num, int target) { 

  int n = num.size(); 

  sort(num.begin(), num.end());

  int sum  = num[0] + num[1] + num[n-1] - target;

  for(int i = 0; i < n -2; i++){

      int start = i + 1, end = n - 1; 
      while(start < end){
                  int temp = num[i] + num[start] + num[end] - target;
                  if(abs(temp) < abs(sum)) sum = temp;
                  if(sum == 0) return target;
                  else if(temp > 0) end--;
                  else start++;
                  }  
  }
 return sum + target; 

} 

3Sum Closest III

Given an array S of n integers, find three integers in S that are 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 is 2. (-1 + 2 + 1 = 2).

求与给定点t距离最近的三个点的和--把点列表每个值x换成|x-t|，则原题转化为求最小的三个值的和---

只需要建三个元素的heap。但求和的时候需要的是x而非|x-t|，两个选择：

1，另建一个flag列表标明每个元素的正负--O(n) space, not good.

2,保持原列表，以|x-t|为条件进行比较。

思路2的c++ code: 

时间复杂度： O(n), 空间复杂度： O(1)

int threeSumClosest(vector<int> &num, int target){
   int sum = 0;
   int maxdist = INT_MAX, maxpt = 0;
 
   for(int i = 0; i < num.size(); i++){
     if(i < 3) {
       sum += num[i];
      }
     if(abs(num[i] - target) < maxdist){
        if(i >= 3){sum = sum + num[i] - num[maxpt];}
        maxdist = abs(num[i] - target);
        maxpt = i;
     }
   }
   return sum;
}