3 Sum Closest

LeetCode笔记 阅读(325)

编号 : 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)`。

Markdown使用 帮助


匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

今天的风儿甚为喧嚣呢。

匿名

我有一头小毛驴,我从来也不骑。

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

我有一头小毛驴,我从来也不骑。

匿名

好!顶!赞!

匿名

好!顶!赞!

匿名

在山的那边,海的那边,有一群蓝精灵。

匿名

好!顶!赞!