16. 3Sum Closest

发表于
这一题和3Sum思路相近，是比较简单的题目，但是当初第一次做3Sum的时候也是看了答案才知道了思路，故在此做下笔记。

题目

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.

例子

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解法

暴力解法

暴力解法是最容易想到的，也最符合正常思路，那就是将数组中的所有三元组都找出来；这样就需要找到$\binom{n}{3}$种组合，所以大致的时间复杂度应该也是$O(n^3)$，这种算法思路简单，但是时间复杂度太大。

先排序后找三元组解法

  1. 这种解法是先将无序的数组变为有序，如果直接调用 C++ algorithm 库中的sort算法，大致排序时间应该是$O(nlgn)$。

  2. 之后在排序过后的数组中寻找三元组，寻找的方法是先固定数组(nums)中的一个元素 $x$ ，然后在该元素的左右分别设置两个下标索引 $l$ 和 $r$ ，当 $x + nums[l] + nums[r] < target$ 时，因为数组经过排序，所以就不用在意 $l$ 之前的元素，可以直接将 $r + 1$ 来寻找下一个三元组；反之亦然。

  3. 这种方法规避了许多不必要的三元组查找，在三元组查找的过程中时间复杂度只有 $O(n^2)$ ，所以该算法最后的时间复杂度是 $O(nlgn) + O(n^2)$ ，即 $O(n^2)$ 。

代码

暴力解法

无

先排序后找三元组解法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = -1; //最终的答案
        int distance = INT_MAX; //距离初始值设为最大
        sort(nums.begin(), nums.end()); //数组排序
        //遍历数组取固定的第一个元素
        for (int i = 1; i < nums.size() - 1; i++) {
            int l = i -1, r = i + 1; //设置两个下标索引
            //在固定一个元素的基础上，左右两个下标索引进行移动
            while (l >= 0 && r < nums.size()) {
                //将寻找到的三元组进行计算并比较和target的距离，取较小值
                if (abs(nums[l] + nums[r] + nums[i] - target) < distance) {
                    distance = abs(nums[l] + nums[r] + nums[i] - target);
                    ans = nums[l] + nums[r] + nums[i];
                }
                //如果三元素之和小于target，则r向右移动
                if (nums[l] + nums[r] + nums[i] < target) {
                    //重复元素直接跳过
                    while (r < nums.size() - 1 && nums[r] == nums[r+1])
                        r++;
                    r++;
                    continue;
                }
                //如果三元素之和大于target，则l向左移动
                if (nums[l] + nums[r] + nums[i] > target) {
                    while (l > 0 && nums[l] == nums[l-1])
                        l--;
                    l--;
                    continue;
                }
                //如果三元素之和刚好等于target，则直接返回即可
                if (nums[l] + nums[r] + nums[i] == target)
                    return target;
            }
        }
        return ans;
    }
};