Description

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:

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 16 3um closest

Solution

Approach 1

这道题与之前的“3Sum”十分类似，做起来思路是非常相似的，最容易想到的就是暴力解法，穷举出所有的组合，进而找出最接近的。

int threeSumClosest(vector<int>& nums, int target) {
    if (nums.size() < 3) {
	return 0;
    }

    int ans = nums[0] + nums[1] + nums[2];
    int diff = abs(target - ans);

    // 穷举出所有的组合，与target比较，找到最接近的
    for (int i=0; i < nums.size(); ++i) {
	for (int j=i+1; j < nums.size(); ++j) {
	    for (int k=j+1; k < nums.size(); ++k) {
		int sum_t = nums[i] + nums[j] + nums[k];
		int diff_t = abs(target - sum_t);

		ans = diff_t < diff ? (diff = diff_t, sum_t) : ans;

		if (ans == target) {
		    return ans;
		}
	    }
	}
    }

    return ans;
}

Approach 2

套用之前“3Sum”的O(n2)解法，下面的解法也是很容易想到的。

int threeSumClosest(vector<int>& nums, int target) {
    if (nums.size() < 3) {
	return 0;
    }

    sort(nums.begin(), nums.end());

    int ans = nums[0] + nums[1] + nums[2];
    int diff = abs(target - ans);

    for (int i=0; i < nums.size(); ++i) {
	int n1 = nums[i];
	int front = i + 1;
	int end = nums.size() - 1;

	while (front < end) {
	    int n2 = nums[front];
	    int n3 = nums[end];
	    int sum = n1 + n2 + n3;
	    int diff_t = abs(target - sum);

	    if (diff > diff_t) {
		ans = sum;
		diff = diff_t;
	    }

	    if (sum == target) {
		return sum;
	    }
	    else if (sum > target) {
		--end;
	    }
	    else {
		++front;
	    }
	}
    }

    return ans;
}