16. 3Sum Closest.md

16. 最接近的三数之和

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

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

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

解法一：

//时间复杂度O(n^2)), 空间复杂度O(n)
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        int res = INT_MAX;
        for(int k = 0; k < n - 2; k++) {
            if(k > 0 && k < n - 2 && nums[k] == nums[k - 1]) k++;
            int i = k + 1, j = n - 1;
            while(i < j) {
                int temp = nums[k] + nums[i] + nums[j] - target;
                if(temp == 0) return target;
                if(abs(temp) < abs(res)) res = temp;
                
                if(temp >= 0) j--;
                else if(temp <= 0) i++;
            }
        }
        return res + target;
    }
};

思路：

解法和第15题几乎一样，不同的地方在于此题条件说有唯一解，所以就不用去重了。

2019/09/19 20:30