16. 最接近的三数之和

[MyLinChi]

题目描述

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

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

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

链接：https://leetcode-cn.com/problems/3sum-closest

方案

思路与三数之和差不多#7，但要注意双指针变化时的判定条件和最小值的求取过程。
这种方法的时间复杂度有点大。

class Solution {
public:
	void fastsort(vector<int>& nums,int a,int b){
		if (a>=b||nums.size()<=1)return;
		int i,j,tmp = nums[a];
		for (i = a, j = b; i < j;){
			while(i<j && nums[j] >= tmp)j--;
			nums[i] = nums[j];
			while (i < j&&nums[i] <= tmp)i++;
			nums[j] = nums[i];
		}
		nums[j] = tmp;
		fastsort(nums,a,j-1);
		fastsort(nums,j+1, b);
	}
	int threeSumClosest(vector<int>& nums, int target) {
		if (nums.size() < 3)return 0;
		fastsort(nums,0,nums.size()-1);
		int a,b,c,res =0,delta = INT_MAX;
		for (a = 0; a+2 < nums.size();a++){
			for (b = a + 1, c = nums.size() - 1; b < c;){
				int de1ta1 = abs(nums[a] + nums[b] + nums[c] - target);
				if (delta > de1ta1){
					delta = de1ta1;
					res = nums[a] + nums[b] + nums[c];
				}
				if (nums[a] + nums[b] + nums[c] < target){
					b++;
				}
				else{
					c--;
				}
			}
		}
		return res;
	}
};