3 Sum Closest

编号 : 16      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given an array `nums` of n integers and an integer `target`, find three integers in `nums` 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).
>

# 解 :  
```Cpp
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        
        /* 为了优化搜索过程，对数据进行排序，同时可以避免重复 */
        sort(nums.begin(), nums.end());
        
        /* 这个初始值是根据后面的搜索过程设定的 */
        int ret = nums[0] + nums[1] + *(nums.end()-1) - target;
        
        for(int x = 0; x < nums.size(); x++)
        {
            /* y和z从两头往中间搜索，逐渐靠近target */
            int y = x + 1;
            int z = nums.size() - 1;
            while(y < z)
            {
                int sum = nums[x] + nums[y] + nums[z];
                
                if(abs(sum - target) < abs(ret - target))
                {
                    ret = sum;
                }
                
                /* 由于数据是有序的，所以
                 * sum > target的时候只能缩小z
                 * sum < target的时候只能增大y
                 */
                if(sum > target)
                {
                    z--;
                }
                else if(sum < target)
                {
                    y++;
                }
                else
                {
                    return target;
                }
            }
        }
        return ret;
    }
};
```

# 分析 :  
这道题的解法和[第15题](http://phosphophyllite.me/article/reading?id=36)一摸一样。

如果采用三层循环嵌套，遍历`x`、`y`、`z`，得出全部的`sum = x + y + z`复杂度为O(n^3)。  

首先对原数据进行排序，`x`遍历数组，`y`和`z`分别放置在剩余范围的两端。  

由于数组是**有序的**需要增大`sum`时只能将`y`向后移动，反之则只能将`z`向前移动。

这样一来对`y`和`z`的搜索复杂度从`O(n^2)`优化为了`O(n)`，整个算法的复杂度变成了`O(n^2)`。