[LeetCode]16. 3Sum Closest

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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. 

1
2
3
4
5
Example:

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

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

给定n个数的数组以及一个整数target, 在数组内查找3个数a,b,c使得三者之和最接近target. 返回这三个数的和. 假设数组中一定存在一个解决方案.

Solution

Analysis

这种K-Sum题,解法类似: 排序+夹逼定理. 先对数组排序, 然后再循环k-2次循环, 内部进行夹逼, 时间复杂度为O(N ** K-1).

由于这里是求3Sum,但并不是等于,而是最接近. 所以至少需要两个变量:一个记录最终结果,一个记录和target之间的绝对值差距.通过循环求和,比较,更新结果变量和差距变量. 也可以只使用一个变量,result; 和target之间的差距每次重新计算, 然后对result更新.

Code

两个变量

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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int result = 0;
        int min_gap = INT_MAX;
        
        sort(nums.begin(), nums.end());

        for (int i=0; i< nums.size(); i++){
            
            if (i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i+1, right = nums.size()-1;
            
            while (left < right){
                int cur = nums[i] + nums[left] + nums[right];
                int gap = abs(target - cur);
                if (gap < min_gap){// 更接近, 更新变量
                    min_gap = gap;
                    result = cur;
                }
                
                if (cur < target)
                    left++;
                else
                    right--;
            }
        }
        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
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int result = nums[0] + nums[1] + nums[2];// 需要记录一个初始值;不能使用INT_MIN,会导致整数越界
        for (int i=0; i< nums.size(); i++){
            int left = i+1, right = nums.size()-1;
            while (left < right){
                int cur = nums[i] + nums[left] + nums[right];
                if (cur == target){
                    result = cur;
                    break;
                }
                else if(abs(target-cur) < abs(target-result))
                    result = cur;
                else if (cur < target)
                    left++;
                else
                    right--;
            }
        }
        return result;
    }
};
您的支持就是我更新的最大动力!谢谢!