力扣16题 ~ 最接近的三数之和

0、前言

本篇博客是力扣上 16.最接近的三数之和 题的题解，写博客主要是想记载看到的一个有意思的解法！

1、题目描述

2、解题思路

2.1 方法1 ~ 暴力求解

2.1.1 思路

先排序，然后三层循环相嵌套，循环查找合适的可能，只不过此方法时间复杂度是O(N^3)，而且该方法超时~

2.1.2 程序代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3)
		    return -1;
        sort(nums.begin(), nums.end());
        int result = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.size() - 2; i++)
        {
            for (int j = i + 1; j < nums.size() - 1; j++)
            {
                for (int k = j + 1; k < nums.size(); k++)
                {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == target)
                    	return target;
                    if (abs(target - result) >= abs(target - sum))
                        result = sum;
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.2 方法2 ~ 双指针

2.2.1 思路

首先对整个数组排序，之后从第一个数开始，若此数索引为i，则从数组的前后开始，设置left = i+1，right = nums.size() - 1 ，如此可得 sum = nums[i] + nums[left] + nums[right] ，然后以 sum 与 target 之间的差值进行判断，遍历寻找差值最小的组合。其中，若 sum > target 则可将 right-- ,反之则 left++。具体代码如下

2.1.2 程序代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) 
	{
		if (nums.size() < 3)
			return -1;
		sort(nums.begin(), nums.end());
		int result = nums[0] + nums[1] + nums[2];
		for (int i = 0; i < nums.size() - 2; i++)
		{
			int left = i + 1;
			int right = nums.size() - 1;
			while (left < right)
			{
				int sum = nums[i] + nums[left] + nums[right];
				if (abs(target - result) >= abs(target - sum))
					result = sum;
				if (sum > target)
					right--;
				else
					left++;
			}
		}
		return result;
	}
};
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