[LeetCode 16] 3Sum Closest

作者 Shilei Tian 日期 2017-06-06
[LeetCode 16] 3Sum 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).

解题思路

这道题很明确,找出数组 nums 中三个元素,使得它们的和与给定值 target 最接近。由于要求元素个数已经确定,所以很容易就想到了时间复杂度为 $\mathcal{O}(n^3)$ 的方法。那么现在问题的关键是,有没有更好时间复杂度的算法呢?

思考一下,按照题目的要求,感觉势必需要遍历所有可能的组合方式。但实际上一定是这样的吗?并不是。我们只需要遍历那些能进一步缩小和目标值之间距离的元素即可。那么如何才能够遍历出所有可能进一步缩小 gap 的元素呢?

考虑,如果这道题目变成,找出两个元素,使得它们的和与给定值最接近,你会不会做?是不是就能立即想到设置两个标记 pq,分别让它们指向数组的开始和结束,然后判断 nums[p] + nums[q]target 的关系来更新 pq

那么现在变成三个元素了,如果设置三个标记 ijk 的话,一下子就不会根据 sum 的值和 target 之间的关系来更新标记了是吧?这里有一个小 trick,我们可以遍历所有可能的 i,然后初始化 j = i + 1k = nums.size() - 1,然后像两个元素那样,更新 jk 即可。这样我们能够找到所有可以进一步缩小 gap 的元素组合。

代码如下:

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int gap = INT_MAX, sum = 0;
for (int i = 0; i < nums.size() - 2; ++i) {
int j = i + 1, k = nums.size() - 1;
while (j < k) {
int sum_ = nums[i] + nums[j] + nums[k];
if (sum_ == target) {
return target;
}
int gap_ = abs(target - sum_);
if (gap_ < gap) {
gap = gap_;
sum = sum_;
}
if (sum_ > target) {
--k;
} else {
++j;
}
}
}
return sum;
}
};

这段代码的运行时间为 12 ms。这里我们再谈谈代码的优化对程序运行时间的影响。

有时候,代码结构上的优化能够带来相当大运行速度上的提升,一点都不亚于引入一个时间复杂度稍微好一点的算法。上面的代码中,对于 sum_target 的判断我这里给分开进行了,在之间插入了对 gap_ 的更新。如果我们将判断写在一起,如下:

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int gap = INT_MAX, sum = 0;
for (int i = 0; i < nums.size() - 2; ++i) {
int j = i + 1, k = nums.size() - 1;
while (j < k) {
int sum_ = nums[i] + nums[j] + nums[k];
if (sum_ == target) {
return target;
} else if (sum_ > target) {
--k;
} else {
++j;
}
int gap_ = abs(target - sum_);
if (gap_ < gap) {
gap = gap_;
sum = sum_;
}
}
}
return sum;
}
};

猜一下,运行时间是多少?答案是:9 ms!提升了 25%!为什么呢?指令流水!详细的讨论我们在这里不展开,有兴趣可以参考《Optimized C++》以及其他的代码级优化的参考资料。