16. 3Sum Closest

发表于 | 分类于

每日一题 2019 - 03 - 06

题目：

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.

Example:

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

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

解法：

这个题跟leetcode 15.3Sum基本是一个思路，不过那个题让求三个数值为0的序列，这个题让求距离给定值最近的三个数的和，思路基本是一样的，不过有一点改变，就是在求值时候可以忽略重复出现的值，也就不用考虑重复出现的序列，所以这种设置双指针获得三重循环效果的思路还是值得记录一下的。

代码：

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 size = nums.size();
        sort(nums.begin(),nums.end());
        if(size <=2 )
        {
            return 0 ;
        }
        int max = abs(nums[0] + nums[1] + nums[2] - target) ;
        int temp = nums[0] + nums[1] + nums[2] ;
        for(int i = 0 ; i < size - 2; i ++ )
        {
            int left = i + 1 ; 
            int right = size - 1 ;
            while (left < right){
                int result = abs(nums[i] + nums[left] + nums[right] - target);
                if( result < max )
                {
                    max = result ;
                    temp = nums[i] + nums[left] + nums[right] ;
                }
                if(nums[i] + nums[left] + nums[right] < target )
                {
                    left ++ ;
                }
                else if(nums[i] + nums[left] + nums[right] > target )
                {
                    right -- ;
                }
                else
                {
                    return nums[i] + nums[left] + nums[right] ;
                }
            }
        }
        return temp  ;
    }
};
0%
undefined