Leetcode-16.最接近的三数之和

发表于 分类于 阅读次数：

题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法1：双指针法

思路与Leetcode-15题基本类似

添加max变量，max为距离最近目标值的差值，始终为正

添加代码m=nums[k]+nums[i]+nums[j]

temp=m-target

1.temp==0即找到等于目标值的组合，直接返回target

2.temp<0 当max>-temp 即当前离目标值更近，更新max为-temp，res为m

3.temp>0 当max>temp 即当前离目标值更近 , 更新max为temp,res为m

其他与15题相同

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int max=INT_MAX;
        int i,j;
        int k=0;
        int res;
        int temp;
        int m;
        if(nums.size()<=2)
            return 0;
        sort(nums.begin(),nums.end());
        for(;k<nums.size()-2;k++)
        {
            if(k>0&&nums[k]==nums[k-1])
                continue;
            i=k+1;
            j=nums.size()-1;
            while(i<j)
            {
                m=nums[k]+nums[i]+nums[j];
                temp=m-target;
                if(temp==0)
                {
                    return target;
                }
                else if(temp<0)
                {
                    
                    if(max>-temp)
                    {
                        max=-temp;
                        res=m;
                    }
                    i++;
                    while(nums[i]==nums[i-1]&&i<j)
                        i++;
                }
                else 
                {
                    if(max>temp)
                    {
                        max=temp;
                        res=m;
                    }
                    j--;
                    while(nums[j]==nums[j+1]&&i<j)
                        j--;
                }
            }
        }
        return res;
    }
};