3 Sum Closest
LeetCode笔记 阅读(464)
编号 : 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)`。