# 3 Sum Closest ### Source - leetcode: [3Sum Closest | LeetCode OJ](https://leetcode.com/problems/3sum-closest/) - lintcode: [(59) 3 Sum Closest](http://www.lintcode.com/en/problem/3-sum-closest/) ~~~ Given an array S of n integers, find three integers in S such that the sum is 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). ~~~ ### 题解1 - 排序 + 2 Sum + 两根指针 + 优化过滤 和 3 Sum 的思路接近，首先对原数组排序，随后将3 Sum 的题拆解为『1 Sum + 2 Sum』的题，对于 Closest 的题使用两根指针而不是哈希表的方法较为方便。对于有序数组来说，在查找 Cloest 的值时其实是有较大的优化空间的。 ### Python ~~~ class Solution: """ @param numbers: Give an array numbers of n integer @param target : An integer @return : return the sum of the three integers, the sum closest target. """ def threeSumClosest(self, numbers, target): result = 2**31 - 1 length = len(numbers) if length < 3: return result numbers.sort() larger_count = 0 for i, item_i in enumerate(numbers): start = i + 1 end = length - 1 # optimization 1 - filter the smallest sum greater then target if start < end: sum3_smallest = numbers[start] + numbers[start + 1] + item_i if sum3_smallest > target: larger_count += 1 if larger_count > 1: return result while (start < end): sum3 = numbers[start] + numbers[end] + item_i if abs(sum3 - target) < abs(result - target): result = sum3 # optimization 2 - filter the sum3 closest to target sum_flag = 0 if sum3 > target: end -= 1 if sum_flag == -1: break sum_flag = 1 elif sum3 < target: start += 1 if sum_flag == 1: break sum_flag = -1 else: return result return result ~~~ ### 源码分析 1. leetcode 上不让自己导入`sys`包，保险起见就初始化了`result`为还算较大的数，作为异常的返回值。 1. 对数组进行排序。 1. 依次遍历排序后的数组，取出一个元素`item_i`后即转化为『2 Sum Cloest』问题。『2 Sum Cloest』的起始元素索引为`i + 1`，之前的元素不能参与其中。 1. 优化一——由于已经对原数组排序，故遍历原数组时比较最小的三个元素和`target`值，若第二次大于`target`果断就此罢休，后面的值肯定越来越大。 1. 两根指针求『2 Sum Cloest』，比较`sum3`和`result`与`target`的差值的绝对值，更新`result`为较小的绝对值。 1. 再度对『2 Sum Cloest』进行优化，仍然利用有序数组的特点，若处于『一大一小』的临界值时就可以马上退出了，后面的元素与`target`之差的绝对值只会越来越大。 ### 复杂度分析 对原数组排序，平均时间复杂度为 O(nlogn)O(n \log n)O(nlogn), 两重`for`循环，由于有两处优化，故最坏的时间复杂度才是 O(n2)O(n^2)O(n2), 使用了`result`作为临时值保存最接近`target`的值，两处优化各使用了一个辅助变量，空间复杂度 O(1)O(1)O(1). ### C++ ~~~ class Solution { public: int threeSumClosest(vector<int> &num, int target) { if (num.size() <= 3) return accumulate(num.begin(), num.end(), 0); sort (num.begin(), num.end()); int result = 0, n = num.size(), temp; result = num[0] + num[1] + num[2]; for (int i = 0; i < n - 2; ++i) { int j = i + 1, k = n - 1; while (j < k) { temp = num[i] + num[j] + num[k]; if (abs(target - result) > abs(target - temp)) result = temp; if (result == target) return result; ( temp > target ) ? --k : ++j; } } return result; } }; ~~~ ### 源码分析 和前面3Sum解法相似，同理使用i,j,k三个指针进行循环。 区别在于3sum中的target为0，这里新增一个变量用于比较哪组数据与target更为相近 ### 复杂度分析 时间复杂度同理为O(n2)O(n^2)O(n2)运行时间 16ms ### Reference - [3Sum Closest | 九章算法](http://www.jiuzhang.com/solutions/3sum-closest/)