[LeetCode系列]3元素最近和问题的O(n^2)解法

给定一个整数数组(长度不小于3) 和 一个目标值, 从数组中找出3个元素, 使得它们的和与目标值最接近, 返回这个和. 可以认为每个输入的组合都是只有唯一解的.

解法思路参考: Finding three elements in an array whose sum is closest to an given number.

我们首先将问题P转化为P': 能否从数组中找到3个元素, 使得它们的和最接近0?

这个转化非常简单, 只需要将原数组中的每个数都减去目标值的1/3即可.

随后我们解决P'的方法如下:

1. 使用快速排序对数组进行排序, 耗费O(nlogn)时间, 这样数组元素就从小到大排列了;
2. 令 i = 0, 选取第i个元素作为基本元素, 令j = i + 1, k = n - 1, 当j < k时, 进行如下操作
   1. 如果num[i], num[j], num[k]的值更接近于0, 我们就更新结果;
   2. 如果三者的值大于0, 我们就令k = k - 1, 这样就可以选择更小的元素进行求和;
   3. 如果小于0, 我们令j = j + 1.
   4. 如果等于0, 返回0, 算法结束.
3. 当 i < n - 2时, i = i + 1, 跳到第2步.

代码:

 

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        int minSum = num[0] + num[1] + num[2];
        
        if (num.size() == 3) return minSum;
        
        int sum = 0;
        sort(num.begin(), num.end());
        // search for the minimal sum of continuous
        for (int i = 0; i < num.size() - 2; i++) {
            int j = i + 1;
            int k = num.size() - 1;
            while (j < k) {
                sum = num[i] + num[j] + num[k];
                if (abs(sum - target) < abs(minSum - target)) {
                    minSum = sum;
                    if (minSum == target) return minSum;
                }
                (sum > target)? k--: j++;
            }
        }
        return minSum;
    }
};